Jerarquía de Chomsky

En la teoría del lenguaje formal, la informática y la lingüística, la jerarquía de Chomsky (también denominada jerarquía de Chomsky-Schützenberger) es una jerarquía de contención de clases de gramáticas formales..

Esta jerarquía de gramáticas fue descrita por Noam Chomsky en 1956. También lleva el nombre de Marcel-Paul Schützenberger, quien desempeñó un papel crucial en el desarrollo de la teoría de los lenguajes formales.

Gramáticas formales

Una gramática formal de este tipo consiste en un conjunto finito de reglas de producción (lado izquierdo → lado derecho), donde cada lado consta de una secuencia finita de los siguientes símbolos:

• un conjunto finito de símbolos no definitivos (indicando que todavía se puede aplicar alguna regla de producción)
• un conjunto finito de símbolos terminales (indicando que no se puede aplicar ninguna regla de producción)
• a inicio símbolo (un símbolo no definitivo distinguido)

Una gramática formal proporciona un esquema axiomático para (o genera) un lenguaje formal, que es un conjunto (generalmente infinito) de secuencias de símbolos de longitud finita que pueden construirse aplicando reglas de producción a otra secuencia de símbolos (que inicialmente contiene solo el símbolo de inicio). Se puede aplicar una regla reemplazando una aparición de los símbolos en su lado izquierdo con los que aparecen en su lado derecho. Una secuencia de aplicaciones de reglas se denomina derivación. Tal gramática define el lenguaje formal: todas las palabras que consisten únicamente en símbolos terminales a los que se puede llegar por una derivación del símbolo inicial.

Los no terminales a menudo se representan con letras mayúsculas, los terminales con letras minúsculas y el símbolo de inicio con S. Por ejemplo, la gramática con terminales {a, b}, no terminales {S, A, B }, reglas de producción

S → AB

S → ε (donde) ε es la cuerda vacía)

A → aS

B → b

y empezar símbolo S, define el lenguaje de todas las palabras de la forma anbn{displaystyle a^{n}b^ {n} (i.e. n copias de a seguido n copias de b).

La siguiente es una gramática más simple que define el mismo idioma:

Terminales {a, b}, No terminales {S}, Símbolo de inicio S, Reglas de producción

S → aSb

S → ε

Como otro ejemplo, una gramática para un subconjunto de juguetes del idioma inglés viene dada por:

terminales

[generado, odio, gran, verde, ideas, lingüistas]

noterminals

{}S, NP, VP, N, V, Adj}

Normas de producción

S → NP VP

NP → Adj NP

NP → N

VP → V NP

VP → V

N → ideas

N → lingüistas

V → generar

V → odio

Adj → genial

Adj → verde

y comienza el símbolo S. Un ejemplo de derivación es

S → NP VP → Adj NP VP → Adj N VP → Adj N V NP → Adj N V Adj NP → Adj N V Adj Adj NP → Adj N V Adj Adj N → genial N V Adj Adj N → grandes lingüistas V Adj Adj N → grandes lingüistas generan Adj Adj N → grandes lingüistas generan grandes Adj N → grandes lingüistas generan gran verde N → grandes lingüistas generan grandes ideas verdes.

Otras secuencias que se pueden derivar de esta gramática son: "las ideas odian a los grandes lingüistas", y "las ideas generan&# 34;. Si bien estas oraciones no tienen sentido, son sintácticamente correctas. Una oración sintácticamente incorrecta (por ejemplo, "ideas ideas great hate") no se puede derivar de esta gramática. Consulte "Las ideas verdes incoloras duermen furiosamente" para un ejemplo similar dado por Chomsky en 1957; consulte Gramática de estructura de frases y Reglas de estructura de frases para obtener más ejemplos de lenguaje natural y los problemas de la gramática formal en esa área.

La jerarquía

Establecer inclusiones descritas por la jerarquía Chomsky

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 lo reconoce y la forma que deben tener sus reglas.

Grammar	Idiomas	Automaton	Reglas de producción (constantes)*	Ejemplos
Tipo-0	Recursivamente enumerable	Máquina de tortuga	γ γ → → α α {displaystyle gamma rightarrow alpha } ()γ γ {displaystyle gamma } non-empty)	L={}wSilenciow{displaystyle L={w foreverw} describe una máquina de Turing terminante}{displaystyle}
Tipo-1	Contexto sensible	Linear-bound non-deterministic Máquina de tortuga	α α Aβ β → → α α γ γ β β {displaystyle alpha Abeta rightarrow alpha gamma beta }	0}}" xmlns="http://www.w3.org/1998/Math/MathML">L={}anbncnSilencion■0}{displaystyle L={a^{n}b^{n}c^{n}0}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2bb63b71ffcba840f36e802aafe4c9951cf9ec38" style="vertical-align: -0.838ex; width:20.198ex; height:2.843ex;"/>
Tipo-2	Sin texto	Automatón de empuje no determinista	A→ → α α {displaystyle Arightarrow alpha }	0}}" xmlns="http://www.w3.org/1998/Math/MathML">L={}anbnSilencion■0}{displaystyle L={a^{n}b^{n}0}}" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/dfafe0fa14e5249f492f5cbde42062ba4904d56f" style="vertical-align: -0.838ex; width:17.973ex; height:2.843ex;"/>
Tipo-3	Recursos ordinarios	Automaton estatal finito	A→ → a{displaystyle Arightarrow {text{a}} y A→ → aB{displaystyle Arightarrow {text{a}B}	L={}anSilencion≥ ≥ 0}{displaystyle L={a^{n}.
* Significado de símbolos: a{displaystyle {text{a}}} = terminal A{displaystyle A}, B{displaystyle B} = no final α α {displaystyle alpha }, β β {displaystyle beta }, γ γ {displaystyle gamma } = cadena de terminales y/o no terminales

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

Todo lenguaje normal 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 adecuadas, lo que significa que existen lenguajes recursivamente enumerables que no son sensibles al contexto, lenguajes sensibles al contexto que no son libres de contexto y lenguajes libres de contexto que no son regulares.

Gramáticas de tipo 0

Las gramáticas de tipo 0 incluyen todas las gramáticas formales. Generan exactamente todos los idiomas que puede reconocer una máquina de Turing. Estos lenguajes también se conocen como lenguajes recursivamente enumerables o reconocibles por Turing. 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.

Gramáticas de tipo 1

Las gramáticas tipo-1 generan lenguajes sensibles al contexto. Estas gramáticas tienen reglas de la forma α α Aβ β → → α α γ γ β β {displaystyle alpha Abeta rightarrow alpha gamma beta } con A{displaystyle A} a nonterminal and α α {displaystyle alpha }, β β {displaystyle beta } y γ γ {displaystyle gamma } strings of terminals and/or nonterminals. Las cuerdas α α {displaystyle alpha } y β β {displaystyle beta } puede estar vacío, pero γ γ {displaystyle gamma } Debe ser indeseable. La regla S→ → ε ε {displaystyle Srightarrow epsilon } se permite si S{displaystyle S. no aparece en el lado derecho de ninguna regla. Los idiomas descritos por estas gramáticas son exactamente todos los idiomas que pueden ser reconocidos por un autómata ligado lineal (una máquina de Turing no determinista cuya cinta está atada por un tiempo constante la longitud de la entrada).

Gramáticas de tipo 2

Las gramáticas tipo-2 generan los idiomas sin contexto. Estas son definidas por reglas de la forma A→ → α α {displaystyle Arightarrow alpha } con A{displaystyle A} ser un no-terminal y α α {displaystyle alpha } 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 texto —o más bien su subconjunto de lenguaje determinista sin contexto— son la base teórica para la estructura de frases de la mayoría de los idiomas de programación, aunque su sintaxis también incluye la resolución de nombres sensibles al contexto debido a declaraciones y alcance. A menudo se utiliza un subconjunto de gramáticas para facilitar el proceso, como un parser LL.

Gramáticas de tipo 3

Las gramáticas tipo-3 generan los idiomas regulares. Tal gramática restringe sus reglas a un único no-terminal en el lado izquierdo y un lado derecho que consiste en un solo terminal, posiblemente seguido por un único no-terminal (derecho regular). Alternativamente, el lado derecho de la gramática puede consistir en un solo terminal, posiblemente precedido por un único no-terminal (izquierda regular). Estos generan los mismos idiomas. Sin embargo, si se combinan reglas irregulares izquierda y reglas regulares derecha, el idioma ya no necesita ser regular. La regla S→ → ε ε {displaystyle Srightarrow varepsilon } también está permitido aquí si S{displaystyle S. no aparece en el lado derecho de ninguna regla. Estos idiomas son exactamente todos los idiomas que se pueden decidir por un autómata estatal finito. Además, esta familia de idiomas formales puede obtenerse mediante expresiones regulares. Los idiomas regulares se utilizan comúnmente para definir patrones de búsqueda y la estructura lexical de los idiomas de programación.