Gramática sensible al contexto

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Tipo de gramática formal

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 CSG pero no por gramáticas libres de contexto. Las gramáticas sensibles al contexto son menos generales (en el mismo sentido) que las gramáticas no restringidas. Por lo tanto, los CSG se posicionan entre las gramáticas sin contexto y sin restricciones en la jerarquía de Chomsky.

Un lenguaje formal que se puede describir mediante una gramática sensible al contexto o, de manera equivalente, mediante una gramática no contractual o un autómata lineal acotado, se denomina lenguaje sensible al contexto. Algunos libros de texto en realidad definen los CSG como no contractuales, aunque no es así como los definió Noam Chomsky en 1959. Esta elección de definición no hace ninguna diferencia en términos de los lenguajes generados (es decir, las dos definiciones son débilmente equivalentes), pero sí hace una diferencia. diferencia en términos de qué gramáticas se consideran estructuralmente sensibles al contexto; este último tema fue analizado por Chomsky en 1963.

Chomsky introdujo las gramáticas sensibles al contexto como una forma de describir la sintaxis del lenguaje natural donde a menudo ocurre que una palabra puede o no ser apropiada en un lugar determinado según el contexto. Walter Savitch ha criticado la terminología "sensible al contexto" como engañosa y propuesta "no borrable" como una mejor explicación de la distinción entre un CSG y una gramática no restringida.

Aunque es bien sabido que ciertas características de los lenguajes (por ejemplo, la dependencia entre series) no están libres de contexto, es una pregunta abierta cuánto poder expresivo de CSG se necesita para capturar la sensibilidad del contexto que se encuentra en lenguas naturales. La investigación posterior en esta área se ha centrado en los lenguajes ligeramente sensibles al contexto más manejables desde el punto de vista computacional. Las sintaxis de algunos lenguajes de programación visual se pueden describir mediante gramáticas gráficas sensibles al contexto.

Definición formal

Una gramática formal G = (N, Σ, P, S), con N un conjunto de símbolos no terminales, Σ un conjunto de símbolos terminales, P un conjunto de reglas de producción y S el símbolo de inicio, es contexto -sensible si todas las reglas en P son de la forma

αAβ → αγβ

con A ∈ N, α,β ∈ (N∪Σ)^* y γ ∈ (N∪Σ)⁺.

Una cadena u ∈ (N∪Σ)^* produce directamente, o deriva directamente to, una cadena v ∈ (N∪Σ)^*, indicada como u ⇒ v, si u se puede escribir como lαAβr, y v se puede escribir como lαγβr, para alguna regla de producción (αAβ→αγβ) ∈ P, y algunas cadenas de contexto l, r ∈ (N∪Σ)^*. Más generalmente, se dice que u produce, o deriva a, v, denotado como u ⇒^* v, si u = u₁ ⇒...⇒ u_n = v para algunos n≥0 y algunas cadenas u₂,..., u_n-1 (N ∪Σ)^*. Es decir, la relación (⇒^*) es la clausura reflexiva transitiva de la relación (⇒).

El lenguaje de la gramática G es el conjunto de todas las cadenas de símbolos terminales derivables de su símbolo inicial, formalmente: L(G) = { w ∈ Σ^*: S ⇒^* w }. Las derivaciones que no terminan en una cadena compuesta solo por símbolos terminales son posibles, pero no contribuyen a L(G).

La única diferencia entre esta definición de Chomsky y la de las gramáticas no restringidas es que γ puede estar vacía en el caso no restringido.

Algunas definiciones de una gramática sensible al contexto solo requieren que para cualquier regla de producción de la forma u → v, la longitud de u sea menor o igual que la longitud de v. Este requisito aparentemente más débil es de hecho débilmente equivalente, consulte Gramática no contratante # Transformación en gramática sensible al contexto.

Además, una regla de la forma

S → λ

Se permite

donde λ representa la cadena vacía y S no aparece en el lado derecho de ninguna regla. La adición de la cadena vacía permite afirmar que los lenguajes sensibles al contexto son un superconjunto adecuado de los lenguajes libres de contexto, en lugar de tener que hacer la afirmación más débil de que todas las gramáticas libres de contexto sin producciones →λ también son gramáticas sensibles al contexto.

El nombre sensible al contexto se explica por α y β que forman el contexto de A y determinan si A se puede reemplazar con γ o no. Esto es diferente de una gramática libre de contexto donde el contexto de un no terminal no se toma en consideración. De hecho, cada producción de una gramática libre de contexto es de la forma V → w donde V es un simple símbolo no terminal, y w es una cadena de terminales y/o no terminales; w puede estar vacío.

Si la posibilidad de agregar la cadena vacía a un idioma se agrega a las cadenas reconocidas por las gramáticas no contratantes (que nunca pueden incluir la cadena vacía), entonces los idiomas en estas dos definiciones son idénticos.

Las gramáticas sensibles al contexto izquierdo y contexto derecho se definen restringiendo las reglas a solo la forma αA → αγ ya solo Aβ → γβ, respectivamente. Los lenguajes generados por estas gramáticas también son la clase completa de lenguajes sensibles al contexto. La equivalencia se estableció por la forma normal de Penttonen.

Ejemplos

Anbncn

La siguiente gramática sensible al contexto, con el símbolo de inicio S, genera el lenguaje canónico no independiente del contexto { aⁿbⁿcⁿ: n ≥ 1 }:

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c

Las reglas 1 y 2 permiten expandir S a aⁿBC(BC)^n-1; las reglas 3 a 6 permiten intercambiar sucesivamente cada CB por BC (se necesitan cuatro reglas para eso ya que una regla CB → BC no encajaría en el esquema αAβ → αγβ); las reglas 7 a 10 permiten reemplazar los no terminales B y C con sus correspondientes terminales b y c respectivamente, siempre y cuando esté en el lugar correcto. Una cadena de generación para aaabbbccc es:

→₂ aSBC

→₂ aaSBCBC

→₁ aaaBCBCBC

→₃ aaaBCZCBC

→₄ aaaBWZCBC

→₅ aaaBWCCBC

→₆ aaaBBCCBC

→₃ aaaBBCCZC

→₄ aaaBBCWZC

→₅ aaaBBCWCC

→₆ aaaBBCBCC

→₃ aaBBCZCC

→₄ aaBBWZCC

→₅ aaBBWCCC

→₆ aaBBBCCC

→₇ aaabBBCCC

→₈ aaaabbBCCC

→₈ aaabbbCCC

→₉ aabbbcCC

→₁₀ aaabbbccC

→₁₀ aaabbbccc

Anbncndn, etc.

Gramáticas más complicadas ${displaystyle CSG}$ se puede utilizar para parse { aⁿbⁿcⁿdⁿ: n ≥ 1 }, y otros idiomas con más letras. Aquí mostramos un enfoque más simple usando gramáticas no contratantes: Comience con un núcleo de producciones regulares generando las formas sententiales ${displaystyle (ABCD)^{n}abcd}$ e incluyen las producciones no contratantes ${displaystyle p_{Da}:Darightarrow aD}$ , ${displaystyle p_{Db}:Dbrightarrow bD}$ , ${displaystyle p_{Dc}:Dcrightarrow cD}$ , ${displaystyle p_{Dd}:Ddrightarrow dd}$ , ${displaystyle p_{Ca}:Carightarrow aC}$ , ${displaystyle p_{Cb}:Cbrightarrow bC}$ , ${displaystyle p_{Cc}:Ccrightarrow cc}$ , ${displaystyle p_{Ba}:Barightarrow aB}$ , ${displaystyle p_{Bb}:Bbrightarrow bb}$ , ${displaystyle p_{Aa}:Aarightarrow aa}$ .

Ambncmdn

Una gramática no contratante (para la cual hay un equivalente) ${displaystyle CSG}$ ) para el idioma ${displaystyle L_{Cross}={a^{m}b^{n}c^{m}d^{n}:mgeq 1,ngeq 1}}$ se define por ${displaystyle p_{1}:Rrightarrow aRC|aC}$ y ${displaystyle p_{3}:Trightarrow BTd|Bd}$ , ${displaystyle p_{5}:CBrightarrow BC}$ , ${displaystyle p_{0}:Srightarrow RT}$ , ${displaystyle p_{6}:aBrightarrow ab}$ , ${displaystyle p_{7}:bBrightarrow bb}$ , ${displaystyle p_{8}:Cdrightarrow cd}$ , ${displaystyle p_{9}:Ccrightarrow cc}$ .

Con estas definiciones, una derivación para ${displaystyle a^{3}b^{2}c^{3}d^{2}}$ es: ${displaystyle SRightarrow _{p_{0}}RTRightarrow _{p_{1}^{2}p_{2}}a^{3}C^{3}TRightarrow _{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}}$ .

A2i

En el Ejemplo 9.5 (p. 224) de (Hopcroft, Ullman, 1979):

${displaystyle Srightarrow [ACaB]}$
${displaystyle {begin{cases} [Ca]arightarrow aa[Ca]\ [Ca][aB]rightarrow aa[CaB]\ [ACa]arightarrow [Aa]a[Ca]\ [ACa][aB]rightarrow [Aa]a[CaB]\ [ACaB]rightarrow [Aa][aCB]\ [CaB]rightarrow a[aCB]end{cases}}}$
${displaystyle [aCB]rightarrow [aDB]}$
${displaystyle [aCB]rightarrow [aE]}$
${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}}}$
${displaystyle [ADa]rightarrow [ACa]}$
${displaystyle {begin{cases} a[Ea]rightarrow [Ea]a\ [aE]rightarrow [Ea]\ [Aa][Ea]rightarrow [AEa]aend{cases}}}$
${displaystyle [AEa]rightarrow a}$

Forma normal de Kuroda

Cada gramática sensible al contexto que no genera la cadena vacía puede transformarse en una débilmente equivalente en la forma normal de Kuroda. "Débilmente equivalente" aquí significa que las dos gramáticas generan el mismo lenguaje. En general, la forma normal no será sensible al contexto, sino que será una gramática sin contracciones.

La forma normal de Kuroda es una forma normal real para gramáticas no contratantes.

Propiedades y usos

Equivalencia a autómata lineal acotado

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). En algunos libros de texto, este resultado se atribuye únicamente a Landweber y Kuroda. Otros lo llaman el teorema de Myhill-Landweber-Kuroda. (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. Kuroda introdujo la noción de LBA no determinista y la equivalencia entre LBA y CSG en 1964).

A partir de 2010, sigue siendo una pregunta abierta si todos los lenguajes sensibles al contexto pueden ser aceptados por un LBA determinista.

Propiedades de cierre

Los lenguajes sensibles al contexto están cerrados bajo el complemento. Este resultado de 1988 se conoce como el teorema de Immerman-Szelepcsényi. Además, están cerrados bajo unión, intersección, concatenación, sustitución, homomorfismo inverso y Kleene plus.

Todo lenguaje recursivamente enumerable L se puede escribir como h(L) para algún lenguaje sensible al contexto L y algo de homomorfismo de cadenas h.

Problemas computacionales

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

El problema del vacío para gramáticas sensibles al contexto (dada una gramática sensible al contexto G, ¿es L(G)=∅ ?) es indecidible.

Como modelo de lenguajes naturales

Savitch ha demostrado el siguiente resultado teórico, en el que basa su crítica de los CSG como base para el lenguaje natural: para cualquier conjunto recursivamente enumerable R, existe un lenguaje/gramática sensible al contexto G que se puede usar como una especie de proxy para probar la membresía en 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 forma parte de R.

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

Se demostró que algunos lenguajes naturales no están libres de contexto, en base a la identificación de las denominadas dependencias seriales cruzadas y fenómenos de codificación ilimitados. Sin embargo, esto no implica necesariamente que toda la clase 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) estrictamente más débiles (que CSG) pueden explicar el fenómeno de las dependencias entre series; uno puede escribir una gramática LCFRS para {aⁿbⁿcⁿdⁿ | n ≥ 1} por ejemplo.

La investigación en curso sobre lingüística computacional se ha centrado en formular 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 libres de contexto acoplados 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 sensibles al contexto.

Más recientemente, la clase PTIME se identificó con gramáticas de concatenación de rangos, que ahora se consideran las más expresivas de las clases de lenguaje sensible al contexto suave.

Contenido relacionado

Más resultados...

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c

1.		S	→	a	B	C
2.		S	→	a	S	B	C
3.	C	B	→	C	Z
4.	C	Z	→	W	Z
5.	W	Z	→	W	C
6.	W	C	→	B	C
7.	a	B	→	a	b
8.	b	B	→	b	b
9.	b	C	→	b	c
10.	c	C	→	c	c