[2018] [Segundo Parcial] [Ejercicio 2]

[2018] [Segundo Parcial] [Ejercicio 2]

de Paula Cianelli Garcia -
Número de respuestas: 1

¡Hola! Tengo la siguiente consulta sobre el 2do parcial 2018 ejercicio 2:

En la parte a) es correcto ver La como un conjunto y contestar así: 

Falso.
- Si la intersección es vacía ⇾  Es regular por lo tanto LC
- Si la intersección no es vacía -> Debe ser LC por ser Lb LC.

Esta respuesta es suficiente? o debo hacer un ejemplo como en la solución. (si es correcta)

En la parte c) la solución dice "Falso. Sea L a = {a k b k c k , k >0} y L d = ∑* - {abc}, siendo ∑={a,b,c}.

Entonces L dc ={abc}. Entonces, L a ∪ L dc = L a , que es R.E. NO Libre de Contexto

-Pero solo sabemos que La es RE no Regular por letra no entiendo por qué asume que La es no libre de contexto


Muchas gracias


En respuesta a Paula Cianelli Garcia

Re: 2do Parcial 2018 ej 2 VoF

de Diego Garat -
hola:

a) la afirmación es genérica y se entiende que "para todo lenguaje La y Lb que cumplen las premisas, se cumple la conclusión" entonces, para probar que la afirmación es falsa, basta dar un contraejemplo, tan particular como uno quiera, que cumpla lo anterior: eso es lo que plantea la solución.
tu demostración no es correcta porque nada te garantiza que la intersección sea LC porque uno de los componentes lo sea.

c) la solución plantea La= {a^k b^k c^k, k >0}, que se prueba en el teórico que no es un lenguaje libre de contexto usando el PL para LC. ese lenguaje, al igual que {a^k b^k , k >0}, se pueden utilizar en las pruebas sabiendo a cuál anillo de la jerarquía de chomsky pertenecen.

saludos,
d.-