chomsky

Noam Chomsky creó la teoría de las gramáticas generativas, la cual es considerada una de las más significativas contribuciones al campo de la lingüística teórica hecha en el siglo XX.
Cuando NoamChomsky formalizó las gramáticas generativas en 1956, las clasificó en cuatro tipos que ahora se conocen como Jerarquía de Chomsky. Las diferencias entre los tipos de gramática es que tienen cada unareglas más restrictivas sobre las producciones y por lo que pueden generar menos lenguajes formales. Las categorías de gramáticas que creo Chomsky van desde el 0 al 3, los cuales se detallan acontinuación.
Entonces sea  una gramática (y ).
Las gramáticas se distinguen solamente en el sistema de producciones que siempre será un conjunto finito.
Gramáticas detipo 0 (sin restricciones o irrestricto), 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 lenguajesson conocidos como lenguajes recursivamente enumerables. 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.

esdecir, se sustituye por lo menos un símbolo no-terminal.

Gramáticas de tipo 1 (gramáticas sensibles al contexto) generan los lenguajes sensibles al contexto. Estas gramáticas tienen reglas de laforma con un no terminal y , cadenas de terminales y no terminales. Las cadenas, pueden ser vacías, pero no puede serlo. La regla está permitida si no aparece en la parte derecha de ningunaregla. 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úmeroentero de veces sobre la longitud de entrada, también conocidas como autómatas linealmente acotados.



es decir, se sustituye un símbolo no-terminal por algo manteniendo el contexto; entonces una...