Describa y explique ampliamente la tipología propuesta por Chomsky al clasificar los diferentes y tipos de lenguajes
La Jerarquía de Chomsky consta de cuatro niveles:
Ø Gramáticas de tipo 0 (sin restricciones), que incluye a todas las gramáticas formales. Estas gramáticas generan todos los lenguajes capaces de ser reconocidos por una máquina de Turing. Los lenguajes son conocidos como lenguajes recursivamente enumerables. Nótese que esta categoría es diferente de la de los lenguajes recursivos, cuya decisión puede ser realizada por una máquina de Turing que se detenga.
Gramáticas de tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto. Estas gramáticas tienen reglas de la forma  con A un no terminal y α, β y γ cadenas de terminales y no terminales. Las cadenas α y β pueden ser vacías, pero γ no puede serlo. La regla  está permitida si S no aparece en la parte derecha de ninguna regla. Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing no determinista cuya cinta de memoria está acotada por un cierto número entero de veces sobre la longitud de entrada.
Ø Gramáticas de tipo 3 (gramáticas regulares) generan los lenguajes regulares. Estas gramáticas se restringen a aquellas reglas que tienen en la parte izquierda un no terminal, y en la parte derecha un solo terminal, posiblemente seguido de un no terminal. La regla también está permitida si S no aparece en la parte derecha de ninguna regla. Estos lenguajes son aquellos que pueden ser aceptados por un autómata finito. También esta familia de lenguajes pueden ser obtenidas por medio de expresiones regulares.
Nótese que el conjunto de gramáticas correspondiente a los lenguajes recursivos no es un miembro de la jerarquía.
Cada lenguaje regular es a su vez libre del contexto, asimismo un lenguaje libre del contexto es también dependiente del contexto, éste es recursivo y a su vez, recursivamente enumerable. Las inclusiones son, sin embargo, propias, es decir, existen en cada nivel lenguajes que no están en niveles anteriores. |
con A un no terminal y γ una cadena de terminales y no terminales. Estos lenguajes son aquellos que pueden ser reconocidos por un 