Jerarquía de Chomsky

La jerarquía de Chomsky es una clasificación de los lenguajes formales y las gramáticas formales , según la cual se dividen en 4 tipos según su complejidad condicional. Propuesto por el profesor del MIT , el lingüista Noam Chomsky .

Clasificación de gramáticas

Según Chomsky, las gramáticas formales se pueden dividir en cuatro tipos. Para atribuir una gramática a un tipo particular, es necesario que todas sus reglas (producciones) correspondan a ciertos esquemas.

Tipo 0 - Ilimitado

Una gramática con una estructura sintagmática G es una estructura algebraica , un cuádruple ordenado (V T , V N , P, S), donde [1] :

$VERMONT}$ — alfabeto (conjunto) de símbolos de terminal — terminales ,
$V_{N}$ — alfabeto (conjunto) de símbolos no terminales — no terminales ,
$V=V_{T}\taza V_{N}$ - diccionario , además $GRAMO$ $V_{T}\cap V_{N}=\varnada$
$PAGS$ es un conjunto finito de producciones (reglas) de la gramática, $P\subconjunto V^{+}\times V^{*}$
$S$ - carácter de inicio ( fuente ).

Aquí está el conjunto de todas las cadenas sobre el alfabeto , y es el conjunto de cadenas no vacías sobre el alfabeto . $V^*$ $V$ $V^{+}$ $V$

El tipo 0 según la clasificación de Chomsky incluye gramáticas no restringidas - gramáticas con estructura sintagmática , es decir, todas las gramáticas formales sin excepción. Las reglas se pueden escribir como:

\alpha \rightarrow \beta

donde es cualquier cadena no vacía que contiene al menos un símbolo no terminal [2] , y es cualquier cadena de símbolos del alfabeto. ${\ estilo de visualización \ alfa \ en V^{+))$ ${\ estilo de visualización \ beta \ en V ^ {*}}$

Debido a su complejidad, tales gramáticas no tienen aplicación práctica.

Tipo 1 - sensible al contexto

Este tipo incluye gramáticas dependientes del contexto (KZ) y gramáticas que no son abreviaturas. Para la gramática , todas las reglas son [3] : $G(V_{T},V_{N},P,S),V=V_{T}\taza V_{N}$

$\alpha A\beta \rightarrow \alpha \gamma \beta$ , donde . Estas gramáticas se conocen como sensibles al contexto. $\alpha ,\beta \en V^{*},\gamma \en V^{+},A\en V_{N}$
$\alpha \rightarrow \beta$ , donde . Tales gramáticas se clasifican como no abreviadas. $\alpha ,\beta \in V^{+},1\leq |\alpha |\leq |\beta |$

Estas clases de gramáticas son equivalentes. Se pueden utilizar en el análisis de textos en lenguajes naturales, pero prácticamente no se utilizan en la construcción de compiladores debido a su complejidad. Para las gramáticas dependientes del contexto, se prueba el enunciado: mediante algún algoritmo, en un número finito de pasos, es posible determinar si una cadena de símbolos terminales pertenece o no a un lenguaje dado.

Tipo 2 - sin contexto

Este tipo incluye gramáticas libres de contexto (CS) . Para la gramática , todas las reglas son: $G(V_{T},V_{N},P,S),V=V_{T}\taza V_{N}$

$A\rightarrow\beta$ , donde (para gramáticas CF no abreviadas) o (para abreviadoras), . Es decir, la gramática permite que solo aparezca un símbolo no terminal en el lado izquierdo de la regla . $\beta\en V^{+}$ $\beta\en V^{*}$ $A\en V_{N}$

Las gramáticas COP se utilizan ampliamente para describir la sintaxis de los lenguajes informáticos (ver análisis sintáctico ).

Tipo 3 - regular

El tercer tipo incluye gramáticas regulares (automáticas), la más simple de las gramáticas formales. Son independientes del contexto, pero con una funcionalidad limitada.

Todas las gramáticas regulares se pueden dividir en dos clases equivalentes, que, para una gramática de tipo III, tendrán reglas de la siguiente forma:

$A\rightarrow B\gamma$ o , donde (para gramáticas lineales a la izquierda). $A\flecha derecha\gamma$ $\gamma \en V_{T}^{*},A,B\en V_{N}$
$A\flecha derecha\gamma B$ ; o , donde (para gramáticas lineales a la derecha). $A\flecha derecha\gamma$ $\gamma \en V_{T}^{*},A,B\en V_{N}$

Las gramáticas regulares se utilizan para describir las construcciones más simples: identificadores , cadenas , constantes , así como lenguajes ensambladores , procesadores de comandos , etc.

Clasificación de lenguas

Los lenguajes formales se clasifican según los tipos de gramáticas que los definen. Sin embargo, un mismo idioma puede estar definido por diferentes gramáticas pertenecientes a diferentes tipos. En este caso, se considera que el lenguaje pertenece al más simple de ellos. Entonces, un lenguaje descrito por una gramática con una estructura de frase, gramáticas sensibles al contexto y libres de contexto será libre de contexto.

Al igual que con las gramáticas, la complejidad de una lengua está determinada por su tipo. Los más complejos son los idiomas con una estructura de frase (esto incluye los idiomas naturales), luego, los idiomas KZ, los idiomas KS y los más simples, los idiomas regulares.

Notas

↑ Cook, Baze, 1990 , pág. 258.264.
↑ Serebryakov V. A., Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoría e implementación de lenguajes de programación. - M. : MZ-Press, 2006. - S. 21. - ISBN 5-94073-094-9 .
↑ Cook, Baze, 1990 , pág. 268.

Literatura

Molchanov A. Yu. Software del sistema. San Petersburgo: Peter, 2006.
John Hopcroft , Rajiv Motwani , Jeffrey Ullman . CAPÍTULO 5. Gramáticas y lenguajes libres de contexto // Introducción a la teoría de autómatas, lenguajes y computación. - M .: "Williams" , 2002. - S. 528. - ISBN 0-201-44124-1 .
Serebryakov V. A. , Galochkin M. P., Gonchar D. R., Furugyan M. G. Teoría e implementación de lenguajes de programación - M.: MZ-Press, 2006, 2ª ed. — ISBN 5-94073-094-9
Robin Hunter . Conceptos básicos del compilador = La esencia de los compiladores. - M .: "Williams" , 2002. - S. 256. - ISBN 5-8459-0360-2 .
Cook D., Baze G. Capítulo 8. Lenguajes y gramáticas // Matemáticas informáticas = Matemáticas informáticas. - M. : Ciencia. Fizmatlit, 1990. - 384 p. — ISBN 5-02-014216-6 .

Lenguajes formales y gramáticas formales
Conceptos generales	Jerarquía de Chomsky Alfabeto Palabra
tipo 0	Gramática ilimitada máquina de Turing lenguaje enumerado Lenguaje resoluble
Tipo 1	Gramática sensible al contexto Lenguaje sensible al contexto Autómata linealmente acotado
Tipo 2	gramática libre de contexto gramática ambigua lenguaje libre de contexto Autómata pushdown ( determinista ) Lema de crecimiento Lema de Ogden teorema de Cook
Tipo 3	gramática regular lenguaje normal Expresión regular Máquina de estados ( determinista , no determinista ) minimización de DFA Determinación de NFA Teorema de Myhill-Nerode
analizando	analizador LL analizador LR Método de descenso recursivo Algoritmo Kok-Younger-Kasami