Como se puede afimar que estos lenguajes son recursivamente enumerables pero no libre contexto?
Buenas,
En respuesta a Francisco Augusto Casarotti Rivero
[2020] [Febrero] [Ejercicio 1]
por alguna razon no se subio la foto, la reenvio
hola:
el método es el de siempre: a) probar que es no es libre de contexto y b) probar que es r.e. (el orden es intercambiable)
para lo primero, normalmente se aplican propiedades. por ejemplo, en ambos casos podrías aplicar el contrarrecíproco del PL para lenguajes libre de contexto o, también, por absurdo, usando la propiedad de que un lenguaje LC intersección un lenguaje regular da por resultado un lenguaje libre de contexto (esto último es mucho más rápido en este caso, asumiendo que {a^n b^n c^n / n nat} no es libre de contexto por lo visto en el teórico).
para lo segundo, tenés que construir una gramática irrestricta que genere al lenguaje o una MT que lo reconozca.
saludos,
d.-