Buenas tardes,
Tengo una duda con respecto a la solución que se plantea en este ejercio, en particular para L3:
La solución comienza diciendo que L3 es un lenguaje libre de contexto no regular. No me queda claro que te permite afirmar que el lenguaje es no regular, ya que no se hace pumping lemma.
Que la gramatica este simplificada y que esta no sea regular, es lo que me permite saber que el lenguaje es no regular?
O se deberia hacer pumping lemma o utilizar propiedades para probar que no lo es?
hola:
los lenguajes regulares son también libres de contexto y recursivamente enumerables... dar una GLC o una GI que genere un lenguaje no es prueba de que ese lenguaje no sea regular.
en el ejercicio no se pide clasificar al lenguaje, por ende no es necesario probar que sea de un tipo o no sea del otro. sin embargo, en todas las evaluaciones ---sean parciales o exámenes--, ustedes tienen que utilizar siempre el modelo "mínimo" según el tipo de lenguaje: AF y GR para lenguajes regulares, APD y GLC para lenguajes libre de contexto pero no regulares, MT y GI para lenguajes r.e. pero no libres de contexto.
en la solución simplemente establece que el lenguaje es libre de contexto pero no regular ---no lo prueba, pero tampoco se pedía--- y luego procede a realizar una gramática y un autómata de acuerdo al anillo de la JC al que pertenece: una gramática libre de contexto y un APD. en este ejercicio dar una MT y una GI hubiese estado mal, por más que reconociese y generase (respectivamente) bien al lenguaje. igualmente estaría mal una GR y un AF, pero por otras razones: seguramente no reconozca/genere al lenguaje dado.
saludos,
d.-
los lenguajes regulares son también libres de contexto y recursivamente enumerables... dar una GLC o una GI que genere un lenguaje no es prueba de que ese lenguaje no sea regular.
en el ejercicio no se pide clasificar al lenguaje, por ende no es necesario probar que sea de un tipo o no sea del otro. sin embargo, en todas las evaluaciones ---sean parciales o exámenes--, ustedes tienen que utilizar siempre el modelo "mínimo" según el tipo de lenguaje: AF y GR para lenguajes regulares, APD y GLC para lenguajes libre de contexto pero no regulares, MT y GI para lenguajes r.e. pero no libres de contexto.
en la solución simplemente establece que el lenguaje es libre de contexto pero no regular ---no lo prueba, pero tampoco se pedía--- y luego procede a realizar una gramática y un autómata de acuerdo al anillo de la JC al que pertenece: una gramática libre de contexto y un APD. en este ejercicio dar una MT y una GI hubiese estado mal, por más que reconociese y generase (respectivamente) bien al lenguaje. igualmente estaría mal una GR y un AF, pero por otras razones: seguramente no reconozca/genere al lenguaje dado.
saludos,
d.-