Hola, tenemos una duda respecto a los ejercicios que aparecen de V/F. Mirando el diagrama de la jerarquía de Chomsky vemos que hay una inclusión de conjuntos lo que me lleva a pensar que aplicando teoría de conjuntos, nos podría ayudar a resolver ese tipo de ejercicios. Eso es válido? Por ej: Si tengo un lenguaje regular intersección otro RE no LLC me daría Regular (intersección de 2 conjuntos, A incluido en B, da el mas chico).
Está bien?
Muchas gracias!
hola:
es cierto que la jerarquía de chomsky te permite resolver algunos ejercicios de verdadero o falso, pero no de la forma en que lo planteás.
en el diagrama de la jerarquía de chomsky, los lenguajes son elementos, puntos, y no conjuntos de elementos, círculos. lo que dice, entonces, es que el conjunto de todos los lenguajes regulares es un subconjunto del conjunto de todos los lenguajes libres de contexto, el conjunto de todos los lenguajes LC es un... en otras palabras, un lenguaje regular es necesariamente libre de contexto, un lenguaje libre de contexto es necesariamente r.e., etc.
los resultados de los lenguajes vistos como conjuntos son otra cosa... en tu ejemplo: tomo A={0^p / p es primo} y B=L(0*). el primero es r.e. pero no es regular, el segundo es regular. la intersección de ambos da A, que no es regular. lo que la JC sí me permite decir es que A es libre de contexto y r.e. por ser regular.
saludos,
d.-
fe de erratas:
lo que la JC sí me permite decir es que B es libre de contexto y r.e. por ser regular.