Clasificar un lenguaje segun la jerarquia de Chomsky

Clasificar un lenguaje segun la jerarquia de Chomsky

de Hugo Sebastian Rodriguez Reyes -
Número de respuestas: 2

Buenas, en varios ejercicios de examen piden clasificar un lenguaje segun la jerarquia de Chomsky y veo que como solucion ponen algo del estilo:

"El lenguaje es Recursivamente Enumerable no Libre de Contexto. Recursivamente Enumerable por la gramatica/automata de la parte b y no Libre de Contexto por el contrareciproco del Pumping Lema para lenguajes Libres de Contexto lo cual demostraremos a continuacion..."

Mi duda es, si bien en la parte b se pide una gramatica/automata y estoy argumentando que es Recursivamente Enumerable porque existe una Gramatica Irrestricta o una Maquina de Turing, se toma como valido ese argumento si no te sale la GI o la MT de la parte b?

Espero se entienda la duda.

En respuesta a Hugo Sebastian Rodriguez Reyes

Re: Clasificar un lenguaje segun la jerarquia de Chomsky

de Leonardo Richero -

Lo importante es tener claro que para categorizar un lenguaje como RE, en la jerarquía de Chomsky hay que probar ambas cosas:

   1) que no es LC, por PL

   2) que es RE, mostrando que existe una GI o MT que lo genera.

Por lo que es necesario dejar por escrito este argumento.

Luego si la gramática o autómata que se piden en las partes b) y c) del ejercicio, tiene errores o no te salen, normalmente esto se evalúa por separado en esa partes, si es que la gramática y el autómata que genera el lenguaje se piden por separado en la letra, como es el caso que tu planteas.