Gramática sensible al contexto

Una gramática sensible al contexto ( CSG ) es una gramática formal en la que los lados izquierdo y derecho de cualquier regla de producción pueden estar rodeados por un contexto de símbolos terminales y no terminales . Las gramáticas sensibles al contexto son más generales que las gramáticas libres de contexto , en el sentido de que hay lenguajes que pueden ser descritos por una CSG pero no por una gramática libre de contexto. Las gramáticas sensibles al contexto son menos generales (en el mismo sentido) que las gramáticas sin restricciones . Por lo tanto, las CSG se posicionan entre las gramáticas libres de contexto y las sin restricciones en la jerarquía de Chomsky . ^[1]

Un lenguaje formal que puede describirse mediante una gramática sensible al contexto o, equivalentemente, mediante una gramática no contráctil o un autómata lineal acotado , se denomina lenguaje sensible al contexto . Algunos libros de texto definen de hecho los CSG como no contráctiles, ^{[2] [3] [4] [5]} aunque no es así como los definió Noam Chomsky en 1959. ^{[6] [7]} Esta elección de definición no supone ninguna diferencia en términos de los lenguajes generados (es decir, las dos definiciones son débilmente equivalentes ), pero sí supone una diferencia en términos de qué gramáticas se consideran estructuralmente sensibles al contexto; esta última cuestión fue analizada por Chomsky en 1963. ^{[8] [9]}

Chomsky introdujo las gramáticas sensibles al contexto como una forma de describir la sintaxis del lenguaje natural , donde a menudo sucede que una palabra puede o no ser apropiada en un lugar determinado dependiendo del contexto. Walter Savitch ha criticado la terminología "sensible al contexto" por ser engañosa y ha propuesto "sin borrado" como una mejor explicación de la distinción entre una CSG y una gramática sin restricciones . ^[10]

Aunque es bien sabido que ciertas características de los lenguajes (por ejemplo, la dependencia entre series ) no son independientes del contexto, es una pregunta abierta qué parte del poder expresivo de los CSG se necesita para capturar la sensibilidad al contexto que se encuentra en los lenguajes naturales. La investigación posterior en esta área se ha centrado en los lenguajes ligeramente sensibles al contexto, más manejables computacionalmente . ^{[ cita requerida ]} Las sintaxis de algunos lenguajes de programación visual se pueden describir mediante gramáticas de grafos sensibles al contexto . ^[11]

Notaremos una gramática formal como , con un conjunto de símbolos no terminales, un conjunto de símbolos terminales, un conjunto de reglas de producción y el símbolo de inicio.${\displaystyle G=(N,\Sigma ,P,S)}$${\estilo de visualización N}$${\estilo de visualización \Sigma}$${\estilo de visualización P}$${\displaystyle S\en N}$

Una cadena produce directamente , o deriva directamente a , una cadena , denotada como , si v puede obtenerse de u mediante una aplicación de alguna regla de producción en P , es decir, si y , donde es una regla de producción, y es la parte izquierda y derecha no afectadas de la cadena, respectivamente. De manera más general, se dice que u produce , o deriva a , v , denotada como , si v puede obtenerse de u mediante la aplicación repetida de reglas de producción, es decir, si para algún n ≥ 0 y algunas cadenas . En otras palabras, la relación es el cierre transitivo reflexivo de la relación .${\displaystyle u\in (N\cup \Sigma )^{*}}$ ${\displaystyle v\in (N\cup \Sigma )^{*}}$${\displaystyle u\Flecha derecha v}$${\displaystyle u=\gamma L\delta}$${\displaystyle v=\gamma R\delta }$${\displaystyle (L\to R)\en P}$${\displaystyle \gamma ,\delta \en (N\cup \Sigma )^{*}}$${\displaystyle u\Rightarrow ^{*}v}$${\displaystyle u=u_{0}\Flecha derecha ...\Flecha derecha u_{n}=v}$${\displaystyle u_{1},...,u_{n-1}\en (N\cup \Sigma )^{*}}$${\displaystyle \Flecha derecha ^{*}}$${\displaystyle \Flecha derecha}$

El lenguaje de la gramática G es el conjunto de todas las cadenas de símbolos terminales derivables a partir de su símbolo inicial, formalmente: . Las derivaciones que no terminan en una cadena compuesta únicamente por símbolos terminales son posibles, pero no contribuyen a L ( G ).${\displaystyle L(G)=\{w\in \Sigma ^{*}\mid S\Rightarrow ^{*}w\}}$

Una gramática formal es sensible al contexto si cada regla en P tiene la forma donde es la cadena vacía , o la forma${\displaystyle S\to \varepsilon }$${\estilo de visualización \varepsilon}$

αγβ → αγβ

con A ∈ N , ^{[nota 1]} , ^{[nota 2]} y . ^{[nota 3]}${\displaystyle \alpha ,\beta \en (N\cup \Sigma \setminus \{S\})^{*}}$${\displaystyle \gamma \en (N\cup \Sigma \setminus \{S\})^{+}}$

El nombre de sensible al contexto se explica por los α y β que forman el contexto de A y determinan si A puede reemplazarse por γ o no. Por el contrario, en una gramática libre de contexto , no hay contexto presente: el lado izquierdo de cada regla de producción es simplemente un no terminal.

No se permite que la cadena γ esté vacía. Sin esta restricción, las gramáticas resultantes se vuelven iguales en potencia a las gramáticas sin restricciones . ^[10]

Una gramática no contráctil es una gramática en la que, para cualquier regla de producción, de la forma u → v , la longitud de u es menor o igual que la longitud de v .

Toda gramática sensible al contexto no es contráctil, mientras que toda gramática no contráctil puede convertirse en una gramática sensible al contexto equivalente; las dos clases son débilmente equivalentes . ^[12]

Algunos autores utilizan el término gramática sensible al contexto para referirse a las gramáticas no contráctiles en general.

Las gramáticas sensibles al contexto izquierdo y derecho se definen restringiendo las reglas a la forma α A → αγ y a la forma A β → γβ, respectivamente. Los lenguajes generados por estas gramáticas también son la clase completa de lenguajes sensibles al contexto. ^[13] La equivalencia fue establecida por Penttonen forma normal . ^[14]

La siguiente gramática sensible al contexto, con símbolo de inicio S , genera el lenguaje canónico no libre de contexto { a ⁿ b ⁿ c ⁿ | n ≥ 1 }: ^{[ cita requerida ]}

Las reglas 1 y 2 permiten convertir S en un ⁿ BC ( BC ) ^{n −1} ; las reglas 3 a 6 permiten intercambiar sucesivamente cada CB por BC ( para ello se necesitan cuatro reglas , ya que una regla CB → BC no encajaría en el esquema α A β → αγβ); las reglas 7 a 10 permiten reemplazar un B o C no terminal por su b o c terminal correspondiente , respectivamente, siempre que esté en el lugar correcto. Una cadena de generación para aaabbccc es:

S

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB República Checa CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB antes de Cristo CBC

→ ₃ aaaBBC República Checa C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB República Checa CC

→ ₄ aaaBB WZ CC

→ ₅ CC de WC aaaBB

→ ₆ aaaBB BC CC

→ ₇ aa desde BBCCC

→ ₈ aaa bb CCBC

→ ₈ aaab bb CCC

→ ₉ aaabb antes de Cristo CC

→ ₁₀ aa ...​

→ ₁₀ aaabbbc cc

Se pueden utilizar gramáticas más complicadas para analizar { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1 } y otros idiomas con incluso más letras. Aquí mostramos un enfoque más simple utilizando gramáticas sin contracción: ^{[ cita requerida ]} Comience con un núcleo de producciones regulares que generen las formas oracionales y luego incluya las producciones sin contracción , , , , , , , , , .${\displaystyle (ABCD)^{n}abcd}$${\displaystyle p_{Da}:Da\rightarrow aD}$${\displaystyle p_{Db}:Db\rightarrow bD}$${\displaystyle p_{Dc}:Dc\rightarrow cD}$${\displaystyle p_{Dd}:Dd\rightarrow dd}$${\displaystyle p_{Ca}:Ca\rightarrow aC}$${\displaystyle p_{Cb}:Cb\rightarrow bC}$${\displaystyle p_{Cc}:Cc\rightarrow cc}$${\displaystyle p_{Ba}:Ba\rightarrow aB}$${\displaystyle p_{Bb}:Bb\rightarrow bb}$${\displaystyle p_{Aa}:Aa\rightarrow aa}$

Una gramática no contráctil (para la cual existe un CSG equivalente) para el lenguaje se define mediante${\displaystyle L_{Cruz}=\{a^{m}b^{n}c^{m}d^{n}\mid m\geq 1,n\geq 1\}}$

${\displaystyle p_{1}:R\rightarrow aRC|aC}$,

${\displaystyle p_{3}:T\rightarrow BTd|Bd}$,

${\displaystyle p_{5}:CB\rightarrow BC}$,

${\displaystyle p_{0}:S\rightarrow RT}$,

${\displaystyle p_{6}:aB\rightarrow ab}$,

${\displaystyle p_{7}:bB\rightarrow bb}$,

${\displaystyle p_{8}:Cd\rightarrow cd}$, y

${\displaystyle p_{9}:Cc\rightarrow cc}$.

Con estas definiciones, una derivación para es: . ^{[ cita requerida ]}$Estilo de visualización a^{3}b^{2}c^{3}d^{2}}$${\ Displaystyle S \ Rightarrow _ {p_ {0}} RT \ Rightarrow _ {p_ {1} ^ {2} p_ {2}} a ^ {3} C ^ {3} T \ Rightarrow _ {p_ {3} p_{4}}a^{3}C^{3}B^{2}d^{2}\Rightarrow _{p_{5}^{6}}a^{3}B^{2}C^ {3}d^{2}\Rightarrow _{p_{6}p_{7}}a^{3}b^{2}C^{3}d^{2}\Rightarrow _{p_{8}p_ {9}^{2}}a^{3}b^{2}c^{3}d^{2}}$

En el Ejemplo 9.5 (p. 224) de (Hopcroft, Ullman, 1979) se construye una gramática no contráctil para el lenguaje { a ^{2 i} | i ≥ 1 }: ^[15]

1. ${\displaystyle S\rightarrow [ACaB]}$
2. ${\displaystyle {\begin{casos}\ [Ca]a\rightarrow aa[Ca]\\\ [Ca][aB]\rightarrow aa[CaB]\\\ [ACa]a\rightarrow [Aa]a[Ca]\\\ [ACa][aB]\rightarrow [Aa]a[CaB]\\\ [ACaB]\rightarrow [Aa][aCB]\\\ [CaB]\rightarrow a[aCB]\end{casos}}}$
3. ${\displaystyle [aCB]\rightarrow [aDB]}$
4. ${\displaystyle [aCB]\rightarrow [aE]}$
5. ${\displaystyle {\begin{cases}\ a[Da]\rightarrow [Da]a\\\ [aDB]\rightarrow [DaB]\\\ [Aa][Da]\rightarrow [ADa]a\\\ a[DaB]\rightarrow [Da][aB]\\\ [Aa][DaB]\rightarrow [ADa][aB]\end{cases}}}$
6. ${\displaystyle [ADa]\rightarrow [ACa]}$
7. ${\displaystyle {\begin{cases}\ a[Ea]\rightarrow [Ea]a\\\ [aE]\rightarrow [Ea]\\\ [Aa][Ea]\rightarrow [AEa]a\end{cases}}}$
8. ${\displaystyle [AEa]\rightarrow a}$

Toda gramática sensible al contexto que no genere la cadena vacía puede transformarse en una gramática débilmente equivalente en la forma normal de Kuroda . "Débilmente equivalente" aquí significa que las dos gramáticas generan el mismo lenguaje. La forma normal en general no será sensible al contexto, sino que será una gramática no contráctil . ^{[16] [17]}

La forma normal de Kuroda es una forma normal real para gramáticas sin contracción.

This section needs additional citations for verification. Please help improve this article by adding citations to reliable sources in this section. Unsourced material may be challenged and removed. (August 2014) (Learn how and when to remove this message)

Un lenguaje formal puede ser descrito por una gramática sensible al contexto si y solo si es aceptado por algún autómata lineal acotado (LBA). ^[18] En algunos libros de texto este resultado se atribuye únicamente a Landweber y Kuroda . ^[7] Otros lo llaman el teorema Myhill -Landweber-Kuroda. ^[19] (Myhill introdujo el concepto de LBA determinista en 1960. Peter S. Landweber publicó en 1963 que el lenguaje aceptado por un LBA determinista es sensible al contexto. ^[20] Kuroda introdujo la noción de LBA no determinista y la equivalencia entre LBA y CSG en 1964. ^{[21] [22]} )

A partir de 2010 ^{[ necesita actualización ]} todavía es una cuestión abierta si cada lenguaje sensible al contexto puede ser aceptado por un LBA determinista . ^[23][update]

Los lenguajes sensibles al contexto están cerrados bajo complemento . Este resultado de 1988 se conoce como el teorema de Immerman–Szelepcsényi . ^[19] Además, están cerrados bajo unión , intersección , concatenación , sustitución , ^{[nota 4]} homomorfismo inverso y Kleene plus . ^[24]

Todo lenguaje enumerable recursivamente L puede escribirse como h ( L ) para algún lenguaje sensible al contexto L y algún homomorfismo de cadenas h . ^[25]

El problema de decisión que pregunta si una determinada cadena s pertenece al lenguaje de una gramática sensible al contexto dada G , es PSPACE-completo . Además, hay gramáticas sensibles al contexto cuyos lenguajes son PSPACE-completos. En otras palabras, hay una gramática sensible al contexto G tal que decidir si una determinada cadena s pertenece al lenguaje de G es PSPACE-completo (por lo que G es fijo y solo s es parte de la entrada del problema). ^[26]

El problema del vacío para gramáticas sensibles al contexto (dada una gramática sensible al contexto G , es L ( G )=∅ ?) es indecidible . ^{[27] [nota 5]}

Savitch ha demostrado el siguiente resultado teórico, en el que basa su crítica de los CSG como base del lenguaje natural: para cualquier conjunto recursivamente enumerable R , existe un lenguaje/gramática sensible al contexto G que puede usarse como una especie de proxy para probar la pertenencia a R de la siguiente manera: dada una cadena s , s está en R si y solo si existe un entero positivo n para el cual sc ⁿ está en G, donde c es un símbolo arbitrario que no es parte de R . ^[10]

Se ha demostrado que casi todos los lenguajes naturales pueden, en general, caracterizarse por gramáticas sensibles al contexto, pero toda la clase de CSG parece ser mucho más grande que los lenguajes naturales. ^{[ cita requerida ]} Peor aún, dado que el problema de decisión mencionado anteriormente para los CSG es PSPACE-completo, eso los hace totalmente inviables para el uso práctico, ya que un algoritmo de tiempo polinomial para un problema PSPACE-completo implicaría P=NP .

Se ha demostrado que algunos lenguajes naturales no son libres de contexto, basándose en la identificación de las llamadas dependencias entre series y fenómenos de mezcla ilimitada . ^{[ cita requerida ]} Sin embargo, esto no implica necesariamente que la clase de CSG sea necesaria para capturar la "sensibilidad al contexto" en el sentido coloquial de estos términos en lenguajes naturales. Por ejemplo, los sistemas de reescritura lineales libres de contexto (LCFRS) son estrictamente más débiles que los CSG, pero pueden dar cuenta del fenómeno de las dependencias entre series; se puede escribir una gramática LCFRS para { a ⁿ b ⁿ c ⁿ d ⁿ | n ≥ 1}, por ejemplo. ^{[28] [29] [30]}

La investigación actual sobre lingüística computacional se ha centrado en la formulación de otras clases de lenguajes que son " ligeramente sensibles al contexto " cuyos problemas de decisión son factibles, como las gramáticas de árboles adyacentes , las gramáticas categoriales combinatorias , los lenguajes acoplados libres de contexto y los sistemas de reescritura lineales libres de contexto . Los lenguajes generados por estos formalismos se encuentran propiamente entre los lenguajes libres de contexto y los sensibles al contexto.

Más recientemente, la clase PTIME se ha identificado con gramáticas de concatenación de rangos , que ahora se consideran las más expresivas de las clases de lenguaje sensibles al contexto moderado. ^[30]

• Jerarquía de Chomsky
• Desarrollar la gramática sensible al contexto
• Gramática de cláusulas definidas#Gramáticas no independientes del contexto
• Lista de generadores de analizadores sintácticos para gramáticas sensibles al contexto

• Meduna, Alexander ; Švec, Martin (2005). Gramáticas con condiciones de contexto y sus aplicaciones . John Wiley & Sons. ISBN 978-0-471-73655-4.

• Análisis de Earley para gramáticas sensibles al contexto