Jerarquía de Chomsky

Jerarquía de clases de gramáticas formales

Inclusiones de conjuntos descritas por la jerarquía de Chomsky

La jerarquía de Chomsky en los campos de la teoría formal del lenguaje , la informática y la lingüística , es una jerarquía de contención de clases de gramáticas formales . Una gramática formal describe cómo formar cadenas a partir del vocabulario (o alfabeto) de un idioma que sean válidas de acuerdo con la sintaxis del mismo. El lingüista Noam Chomsky teorizó que existían cuatro clases diferentes de gramáticas formales que podían generar idiomas cada vez más complejos. Cada clase también puede generar por completo el idioma de todas las clases inferiores (conjunto incluido).

Historia

La idea general de una jerarquía de gramáticas fue descrita por primera vez por Noam Chomsky en "Tres modelos para la descripción del lenguaje". ^[1] Marcel-Paul Schützenberger también jugó un papel en el desarrollo de la teoría de los lenguajes formales ; el artículo "La teoría algebraica de los lenguajes libres de contexto" ^[2] describe la jerarquía moderna, incluidas las gramáticas libres de contexto. ^[3]

De manera independiente, junto con los lingüistas, los matemáticos estaban desarrollando modelos de computación (a través de autómatas ). Analizar una oración en un idioma es similar a la computación, y las gramáticas descritas por Chomsky demostraron ser similares y equivalentes en potencia computacional a varios modelos de máquinas. ^[4]

La jerarquía

La siguiente tabla resume cada uno de los cuatro tipos de gramática de Chomsky, la clase de lenguaje que genera, el tipo de autómata que lo reconoce y la forma que deben tener sus reglas. Las clases se definen por las restricciones de las reglas de producción.

1. Significado de los símbolos:
   • ${\displaystyle {\text{a}}}$= terminal
   • ${\displaystyle A}$, = no terminal ${\displaystyle B}$
   • ${\displaystyle \alpha }$, , = cadena de terminales y/o no terminales ${\displaystyle \beta }$ ${\displaystyle \gamma }$

Nótese que el conjunto de gramáticas correspondientes a lenguajes recursivos no es miembro de esta jerarquía; estos estarían propiamente entre Tipo-0 y Tipo-1.

Todo lenguaje regular es independiente del contexto, todo lenguaje independiente del contexto es sensible al contexto, todo lenguaje sensible al contexto es recursivo y todo lenguaje recursivo es recursivamente enumerable. Todas estas son inclusiones propias, lo que significa que existen lenguajes recursivamente enumerables que no son sensibles al contexto, lenguajes sensibles al contexto que no son independientes del contexto e lenguajes independientes del contexto que no son regulares. ^[7]

Gramáticas regulares (tipo 3)

Las gramáticas de tipo 3 generan los lenguajes regulares . Dicha gramática restringe sus reglas a un único no terminal en el lado izquierdo y un lado derecho que consiste en un único terminal, posiblemente seguido por un único no terminal, en cuyo caso la gramática es regular derecha . Alternativamente, todas las reglas pueden tener sus lados derechos que consisten en un único terminal, posiblemente precedido por un único no terminal ( regular izquierda ). Estos generan los mismos lenguajes. Sin embargo, si se combinan las reglas regulares izquierdas y las reglas regulares derechas, el lenguaje ya no necesita ser regular. La regla también se permite aquí si no aparece en el lado derecho de ninguna regla. Estos lenguajes son exactamente todos los lenguajes que pueden ser decididos por un autómata de estados finitos . Además, esta familia de lenguajes formales puede obtenerse mediante expresiones regulares . Los lenguajes regulares se utilizan comúnmente para definir patrones de búsqueda y la estructura léxica de los lenguajes de programación. ${\displaystyle S\rightarrow \varepsilon }$ ${\displaystyle S}$

Por ejemplo, el lenguaje regular es generado por la gramática Tipo-3 con las siguientes producciones . ${\displaystyle L=\{a^{n}|n>0\}}$ ${\displaystyle G=(\{S\},\{a,b\},P,S)}$ ${\displaystyle P}$

S → como

S → un

Gramáticas libres de contexto (tipo 2)

Las gramáticas de tipo 2 generan los lenguajes libres de contexto . Estos se definen mediante reglas de la forma con ser un no terminal y ser una cadena de terminales y/o no terminales. Estos lenguajes son exactamente todos los lenguajes que pueden ser reconocidos por un autómata de inserción no determinista . Los lenguajes libres de contexto, o más bien su subconjunto de lenguajes libres de contexto deterministas , son la base teórica para la estructura de frases de la mayoría de los lenguajes de programación , aunque su sintaxis también incluye la resolución de nombres sensible al contexto debido a las declaraciones y el alcance . A menudo se utiliza un subconjunto de gramáticas para facilitar el análisis, como por ejemplo mediante un analizador LL . ${\displaystyle A\rightarrow \alpha }$ ${\displaystyle A}$ ${\displaystyle \alpha }$

Por ejemplo, el lenguaje libre de contexto es generado por la gramática Tipo-2 con las siguientes producciones. ${\displaystyle L=\{a^{n}b^{n}|n>0\}}$ ${\displaystyle G=(\{S\},\{a,b\},P,S)}$ ${\displaystyle P}$

S → aSb

S → ab

El lenguaje es libre de contexto pero no regular (según el lema de bombeo para lenguajes regulares ).

Gramáticas sensibles al contexto (tipo 1)

Las gramáticas de tipo 1 generan lenguajes sensibles al contexto . Estas gramáticas tienen reglas de la forma con un no terminal y , y cadenas de terminales y/o no terminales. Las cadenas y pueden estar vacías, pero no deben estar vacías. La regla está permitida si no aparece en el lado derecho de ninguna regla. Los lenguajes descritos por estas gramáticas son exactamente todos los lenguajes que pueden ser reconocidos por un autómata lineal acotado (una máquina de Turing no determinista cuya cinta está acotada por una constante multiplicada por la longitud de la entrada). ${\displaystyle \alpha A\beta \rightarrow \alpha \gamma \beta }$ ${\displaystyle A}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle S\rightarrow \epsilon }$ ${\displaystyle S}$

Por ejemplo, el lenguaje sensible al contexto es generado por la gramática Tipo-1 con las siguientes producciones. ${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$ ${\displaystyle G=(\{S,A,B,C,W,Z\},\{a,b\},P,S)}$ ${\displaystyle P}$

S → aBC

S → aSBC

CB → República Checa

República Checa → República Checa

WZ → WC

WC → BC

aB → ab

bB → bB

antes de Cristo → antes de Cristo

cC → cC

El lenguaje es sensible al contexto, pero no independiente del contexto (según el lema de bombeo para lenguajes independientes del contexto ). En el artículo Gramáticas sensibles al contexto se esboza una prueba de que esta gramática genera algo . ${\displaystyle L=\{a^{n}b^{n}c^{n}|n>0\}}$

Gramáticas recursivamente enumerables (Tipo 0)

Las gramáticas de tipo 0 incluyen todas las gramáticas formales. No hay restricciones en las reglas de producción. Generan exactamente todos los lenguajes que pueden ser reconocidos por una máquina de Turing , por lo tanto, cualquier lenguaje que sea posible generar puede ser generado por una gramática de tipo 0. ^[8] Estos lenguajes también se conocen como lenguajes recursivamente enumerables o lenguajes reconocibles por Turing . ^[8] Nótese que esto es diferente de los lenguajes recursivos , que pueden ser decididos por una máquina de Turing que siempre se detiene .

Véase también

• Forma normal de Chomsky

Citas

1. Chomsky 1956.
2. Chomsky y Schützenberger 1963.
3. Allott, Nicholas; Lohndal, Terje; Rey, Georges (27 de abril de 2021). «Introducción sinóptica». Un compañero para Chomsky. págs. 1–17. doi :10.1002/9781119598732.ch1. ISBN 9781119598701. Número de identificación del sujeto  241301126.
4. Kozen, Dexter C. (2007). Autómatas y computabilidad. Textos de pregrado en informática. Springer. pp. 3-4. ISBN 978-0-387-94907-9.
5. Geuvers, H.; Rot, J. (2016). "Aplicaciones, jerarquía de Chomsky y recapitulación" (PDF) . Lenguajes regulares . Archivado (PDF) desde el original el 19 de noviembre de 2018.
6. Sudkamp, ​​Thomas A. (1997) [1988]. Lenguajes y máquinas: Introducción a la teoría de la informática . Reading, Massachusetts, EE. UU.: Addison Wesley Longman. pág. 310. ISBN 978-0-201-82136-9.
7. Chomsky, Noam (1963). "Capítulo 12: Propiedades formales de las gramáticas". En Luce, R. Duncan; Bush, Robert R.; Galanter, Eugene (eds.). Manual de psicología matemática . Vol. II. John Wiley and Sons, Inc. págs. 323–418.
8. Sipser, Michael (1997). Introducción a la teoría de la computación (1.ª ed.). Cengage Learning. pág. 130. ISBN 0-534-94728-XLa tesis de Church -Turing

Referencias

• Chomsky, Noam (1956). "Tres modelos para la descripción del lenguaje" (PDF) . IRE Transactions on Information Theory . 2 (3): 113–124. doi :10.1109/TIT.1956.1056813. S2CID  19519474. Archivado (PDF) desde el original el 7 de marzo de 2016.
• Chomsky, Noam (1959). "Sobre ciertas propiedades formales de las gramáticas" (PDF) . Información y Control . 2 (2): 137–167. doi : 10.1016/S0019-9958(59)90362-6 .
• Chomsky, Noam ; Schützenberger, Marcel P. (1963). "La teoría algebraica de los lenguajes libres de contexto". En Braffort, P.; Hirschberg, D. (eds.). Programación informática y sistemas formales (PDF) . Ámsterdam: Holanda Septentrional. pp. 118–161. Archivado (PDF) desde el original el 13 de junio de 2011.