Jererquia De Chomsky

Jerarquía de Chomsky
Gramáticas Formales
Una gramática formal consta de un conjunto finito e infinito de símbolos terminales (las palabras en un lenguaje formal), un conjunto finito de símbolos noterminales, un conjunto de reglas de producción con un lado izquierdo y otro derecho, y un símbolo inicial.
Ej: El lenguaje “Número” es simplemente el conjunto infinito de cadenas finitas formadascon los dígitos 0, 1, 2, 3, 4, 5, 6, 7, 8 y 9. Dichas cadenas están formadas gracias a un alfabeto y una gramática que están formalmente especificados
El alfabeto es un conjunto finito no vacío desímbolos asimismo la gramática es un conjunto finito de reglas para formar cadenas finitas juntando símbolos del alfabeto, a cada cadena de símbolos de un lenguaje formal se le llama fórmula bien formada(o palabra) del lenguaje
Jerarquía de Chomsky
Es una forma de clasificación de gramáticas en los tipos de lenguajes, esta fue elaborada por Noam Chomsky un estadounidense lingüista, filosofo yactivista.
Chomsky Clasificó los lenguajes en 4 tipos conforme a la gramática generada.
* Tipo 0:
También es conocida como recursivamente enumerables, son los lenguajes naturales. Las gramáticaspueden tener reglas compresoras. Una característica es que no poseen restricciones. Generan todos los lenguajes que pueden ser reconocidos por una máquina de Turing.
* Tipo 1:
También conocidoscomo Lenguajes dependientes del contexto o sensibles al contexto, en estos no existen reglas compresoras, salvo, opcionalmente, la que deriva el axioma a la palabra vacía. Existen reglas en las que unsímbolo no terminal puede derivar a formas senténciales distintas, según los símbolos que aparezcan a su alrededor. Estos lenguajes son todos los lenguajes que pueden ser reconocidos por una máquinade Turing no determinista. (Autómatas lineales acotados)
* Tipo 2:
También conocidos como Lenguajes independientes del contexto o de contexto libre, la mayoría de los lenguajes de programación...