Jerarquía chomsky

Jerarquía de clases de gramáticas formales.

Conjunto de inclusiones descritas por la jerarquía de Chomsky

La jerarquía de Chomsky (con poca frecuencia denominada jerarquía de Chomsky-Schützenberger ^[1] ) en los campos de la teoría del lenguaje formal , 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 según la sintaxis del idioma. El lingüista Noam Chomsky teorizó que existían cuatro clases diferentes de gramáticas formales que podían generar lenguajes cada vez más complejos. Cada clase también puede generar completamente el lenguaje de todas las clases inferiores (conjunto incluido).

Historia

La idea general de una jerarquía de gramáticas fue descrita por primera vez por el lingüista Noam Chomsky en "Tres modelos para la descripción del lenguaje". ^[2] 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" ^[3] describe la jerarquía moderna que incluye gramáticas libres de contexto. ^[1]

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

La jerarquía

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

Tenga en cuenta que el conjunto de gramáticas correspondientes a lenguajes recursivos no es miembro de esta jerarquía; estos estarían correctamente entre el Tipo 0 y el Tipo 1.

Todo lenguaje normal está libre de contexto, todo lenguaje libre de contexto es sensible al contexto, todo lenguaje sensible al contexto es recursivo y todo lenguaje recursivo es recursivamente enumerable. Todas estas son inclusiones adecuadas, lo que significa que existen lenguajes recursivamente enumerables que no son sensibles al contexto, lenguajes sensibles al contexto que no están libres de contexto y lenguajes libres de contexto que no son regulares. ^[7]

Gramáticas regulares (tipo 3)

Las gramáticas de tipo 3 generan los lenguajes regulares . Tal gramática restringe sus reglas a un solo no terminal en el lado izquierdo y un lado derecho que consta de un solo terminal, posiblemente seguido por un solo no terminal, en cuyo caso la gramática es regular hacia la derecha . Alternativamente, todas las reglas pueden tener sus lados derechos compuestos por un único terminal, posiblemente precedido por un único no terminal ( izquierdo regular ). Estos generan los mismos idiomas. Sin embargo, si se combinan reglas regulares de izquierda y reglas regulares de derecha, el lenguaje ya no necesita ser regular. La regla también está permitida 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 se puede obtener 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 y las producciones son las siguientes. ${\displaystyle L=\{a^{n}|n>0\}}$ ${\displaystyle G=(\{S\},\{a,b\},P,S)}$ ${\displaystyle P}$

S → comoS

S → un

Gramáticas libres de contexto (tipo 2)

Las gramáticas de tipo 2 generan lenguajes libres de contexto . Estos se definen mediante reglas de la forma ser un no terminal y ser una cadena de terminales y/o no terminales. Estos idiomas son exactamente todos los idiomas que pueden ser reconocidos por un autómata pushdown no determinista . Los lenguajes libres de contexto, o más bien su subconjunto de lenguajes deterministas libres de contexto , 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 y las producciones son las siguientes. ${\displaystyle L=\{a^{n}b^{n}|n>0\}}$ ${\displaystyle G=(\{S\},\{a,b\},P,S)}$ ${\displaystyle P}$

S → aSb

S → ab

El lenguaje no tiene contexto pero no es 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 estarlo. 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 acotado lineal (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 y las producciones son las siguientes. ${\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 → CZ

CZ → WZ

WZ → WC

WC → antes de Cristo

aB → ab

bB → bb

antes de Cristo → antes de Cristo

cC → cc

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

Gramáticas recursivamente enumerables (tipo 0)

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

Ver también

• Forma normal de Chomsky

Citas

1. Allott, Nicolás; Lohndal, Terje; Rey, Georges (27 de abril de 2021). "Introducción sinóptica". Un compañero de Chomsky : 1–17. doi :10.1002/9781119598732.ch1. ISBN 9781119598701. S2CID  241301126.
2. Chomsky 1956.
3. Chomsky y Schützenberger 1963.
4. Kozen, Dexter C. (2007). Autómatas y computabilidad. Textos de Pregrado en Informática. Saltador. págs. 3–4. ISBN 978-0-387-94907-9.
5. Geuvers, H.; Rot, J. (2016). "Aplicaciones, jerarquía de Chomsky y resumen" (PDF) . Idiomas habituales . Archivado (PDF) desde el original el 19 de noviembre de 2018.
6. Sudkamp, ​​Thomas A. (1997) [1988]. Lenguajes y máquinas: una introducción a la teoría de la informática . Reading, Massachusetts, EE.UU.: Addison Wesley Longman. pag. 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, Eugenio (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.). Aprendizaje Cengage. pag. 130.ISBN​ 0-534-94728-X. La tesis de Church-Turing

Referencias

• Chomsky, Noam (1956). «Tres modelos para la descripción del lenguaje» (PDF) . Transacciones IRE sobre teoría de la información . 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 determinadas 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 del Norte. págs. 118-161. Archivado (PDF) desde el original el 13 de junio de 2011.