Automatas

En lingüística la jerarquía de Chomsky es una clasificación jerárquica de distintos tipos de gramáticas formales que generan lenguajes formales. Esta jerarquía fue descrita por Noam Chomsky en 1956.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 capacesde 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, cuyadecisió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 tienenreglas de la forma [pic] 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 [pic] está permitida si S no aparece enla parte derecha de ninguna regla. Los lenguajes descritos por estas gramáticas son exactamente todos aquellos lenguajes reconocidos por una máquina de Turing determinista cuya cinta de memoria estáacotada por un cierto número entero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados.
▪ Gramáticas de tipo 2 (gramáticas libres del contexto) generanlos lenguajes independientes del contexto. Las reglas son de la forma [pic] con A un no terminal y γ una cadena de terminales y no terminales. Estos lenguajes son aquellos que pueden ser reconocidos porun autómata con pila.
▪ 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, yen la parte derecha un solo terminal, posiblemente seguido de un no terminal. La regla [pic] también está permitida si S no aparece en la parte derecha de ninguna regla. Estos lenguajes son...