Chomsky

7.3. La jerarqua de Chomsky
Para concluir el Captulo, damos el que se conoce como Teorema de la
Jerarqua de Chomsky. Dicho Teorema establece las relaciones de contenido
entre los diversostipos de lenguajes que se han introducido a lo largo de
los presentes apuntes. La demostracion del mismo se sigue de los distintos
contenidos que hemos ido viendo.
Teorema 126 (La jerarqua deChomsky) Se tienen las siguientes armaciones:
1. La familia de los lenguajes regulares esta estrictamente contenida en la
familia de los lenguajes independientes del contexto.
2. La familia de loslenguajes independientes del contexto (que no contienen
la palabra vaca) esta estrictamente contenida en la familia de los
lenguajes sensibles al contexto.
3. La familia de los lenguajes sensiblesal contexto esta estrictamente contenida
7.3. La jerarqua de Chomsky
Para concluir el Captulo, damos el que se conoce como Teorema de la
Jerarqua de Chomsky. Dicho Teorema establece lasrelaciones de contenido
entre los diversos tipos de lenguajes que se han introducido a lo largo de
los presentes apuntes. La demostracion del mismo se sigue de los distintos
contenidos que hemos idoviendo.
Teorema 126 (La jerarqua de Chomsky) Se tienen las siguientes armaciones:
1. La familia de los lenguajes regulares esta estrictamente contenida en la
familia de los lenguajesindependientes del contexto.
2. La familia de los lenguajes independientes del contexto (que no contienen
la palabra vaca) esta estrictamente contenida en la familia de los
lenguajes sensibles al contexto.3. La familia de los lenguajes sensibles al contexto esta estrictamente contenida
en la familia de los lenguajes recursivamente enumerables.
7.4. Ejercicios
Ejercicio 44 Para cada uno de lossiguientes lenguajes dar una gramatica
general que los genere:
fa(i)b(i) : i  0g,
fa(i)b(2i) : i  0g,
fa(i)b(i)c(i) : i  0g,
7.4. EJERCICIOS 91
fa(i)b(i2) : i  0g, y
fa(i)b(2i ) : i  0g....