jerarquía de chomsky

INDICE GENERAL





Jerarquía de Chomsky

En lingüística la jerarquía de Chomsky (ocasionalmente también llamada la jerarquía de Chomsky–Schützenberger) 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.
1. Lenguajes y gramáticas
1.1 Lenguajes recursivamente enumerables (detipo 0)
Incluyen todas las gramáticas formales. Generan todos los lenguajes que pueden ser reconocidos por una máquina de Turing.
1.2 Lenguajes dependientes del contexto (de tipo 1)
Generan los lenguajes dependientes de contexto. Contienen reglas de producción de la forma:
 A    
A es un no terminal
,  y  son cadenas de terminales y no terminales.
 y  pueden ser vacíos, pero  hade ser distinto del vacío.
Se denominan gramáticas dependientes del contexto, porque, como se observa, A puede ser sustituido por  si está acompañada de  por la izquierda y de  por la derecha.
Estos lenguajes son todos los lenguajes que pueden ser reconocidos por una máquina de Turing no determinista. (Autómatas lineales acotados)
1.3 Lenguajes independientes del contexto (de tipo 2)Generan los lenguajes libres de contexto. Están definidas por reglas de la forma:
A  
A es un no terminal
 Es una cadena de terminales y no terminales.
Se denominan independientes de contexto porque A puede sustituirse por  independientemente de las cadenas por las que esté acompañada.
Los lenguajes independientes de contexto constituyen la base teórica para la sintaxis de la mayoría delos lenguajes de programación. Definen la sintaxis de las declaraciones, las proposiciones, las expresiones, etc. (es decir, la estructura de un programa)
Estos lenguajes son todos los lenguajes que pueden ser reconocidos por los autómatas de pila.
1.4 Lenguajes regulares (de tipo 3)
Generan los lenguajes regulares. Las reglas se restringen a un único no terminal en la parte izquierda y unaparte derecha compuesta por un único terminal que puede estar seguido o no de un único no terminal. Es decir, normas del tipo:
A a B
A  a
Estos lenguajes son los que pueden ser decididos por un autómata finito (regular). Los lenguajes regulares se utilizan para definir estructura léxica de los lenguajes de programación. Definen la sintaxis de los identificadores, número, cadenas y otrossímbolos básicos del lenguaje.
2. Autómatas
2.1 Máquinas de Turing
Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo a una tabla de reglas. A pesar de su simplicidad, una máquina de Turing puede ser adaptada para simular la lógica de cualquier algoritmo de computador y es particularmente útil en la explicación de las funciones de un CPU dentro de uncomputador.
Una máquina de Turing que es capaz de simular cualquier otra máquina de Turing es llamada una máquina universal de Turing (UTM, o simplemente una máquina universal). Una definición más matemáticamente orientada, con una similar naturaleza "universal", fue presentada por Alonzo Church, cuyo trabajo sobre el cálculo lambda se entrelaza con el de Turing en una formal teoría de la computaciónconocida como la tesis de Church-Turing. La tesis señala que las máquinas de Turing de hecho capturan la noción informal de un método eficaz en la lógica y las matemáticas y proporcionan una precisa definición de un algoritmo o 'procedimiento mecánico'.
2.2 Autómata Linealmente Acotado
Los autómatas linealmente acotados son similares a una máquina de Turing, sabemos que ésta última tiene unacinta infinita.
Un autómata linealmente acotado es una máquina de Turing cuya cinta está formada solamente por celdas de kn de largo, donde la longitud n es la secuencia de la entrada y k es una constante asociada al autómata linealmente-acotado particular, es decir la cantidad de cinta que el autómata permite usar se limita por un factor lineal k para que cuando entre una palabra de tamaño n...