Gramática sensible al contexto

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 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]

Definición formal

Gramática formal

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)}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle P}$ ${\displaystyle S\in 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\Rightarrow v}$ ${\displaystyle u=\gamma L\delta }$ ${\displaystyle v=\gamma R\delta }$ ${\displaystyle (L\to R)\in P}$ ${\displaystyle \gamma ,\delta \in (N\cup \Sigma )^{*}}$ ${\displaystyle u\Rightarrow ^{*}v}$ ${\displaystyle u=u_{0}\Rightarrow ...\Rightarrow u_{n}=v}$ ${\displaystyle u_{1},...,u_{n-1}\in (N\cup \Sigma )^{*}}$ ${\displaystyle \Rightarrow ^{*}}$ ${\displaystyle \Rightarrow }$

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\}}$

Gramática sensible al contexto

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 }$ ${\displaystyle \varepsilon }$

αγβ → αγβ

con A ∈ N , ^{[nota 1]} , ^{[nota 2]} y . ^{[nota 3]} ${\displaystyle \alpha ,\beta \in (N\cup \Sigma \setminus \{S\})^{*}}$ ${\displaystyle \gamma \in (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]

Definiciones (débilmente) equivalentes

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]

Ejemplos

un n b n c n

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

un n b n c n d n, etc.

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}$

un m b n c m d n

Una gramática no contráctil (para la cual existe un CSG equivalente) para el lenguaje se define mediante ${\displaystyle L_{Cross}=\{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 ]} ${\displaystyle 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}}$

a2 yo

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{cases}\ [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{cases}}}$
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}$

Forma normal de Kuroda

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.

Propiedades y usos

Equivalencia con 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). ^[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]

Propiedades del cierre

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]

Problemas computacionales

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]}

Como modelo de los lenguajes naturales

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]

Véase también

• 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

Notas

1. es decir, A un único no terminal
2. es decir, cadenas α y β de no terminales (excepto el símbolo de inicio) y terminales
3. es decir, γ es una cadena no vacía de no terminales (excepto el símbolo de inicio) y terminales
4. más formalmente: si L ⊆ Σ ^* es un lenguaje sensible al contexto y f asigna cada a ∈Σ a un lenguaje sensible al contexto f ( a ), f ( L ) es nuevamente un lenguaje sensible al contexto
5. Esto también se desprende de (1) que los lenguajes libres de contexto también son sensibles al contexto, (2) que los lenguajes sensibles al contexto están cerrados bajo intersección, pero (3) que la disyunción de los lenguajes libres de contexto es indecidible .

Referencias

1. (Hopcroft, Ullman, 1979); Sección 9.4, pág. 227
2. Linz, Peter (2011). Introducción a los lenguajes formales y autómatas. Jones & Bartlett Publishers. pág. 291. ISBN 978-1-4496-1552-9.
3. Meduna, Alexander (2000). Autómatas y lenguajes: teoría y aplicaciones. Springer Science & Business Media. pág. 730. ISBN 978-1-85233-074-3.
4. Davis, Martin ; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica (2.ª ed.). Morgan Kaufmann. pág. 189. ISBN 978-0-08-050246-5.
5. Martin, John C. (2010). Introducción a los lenguajes y la teoría de la computación (4.ª ed.). Nueva York, NY: McGraw-Hill. pág. 277. ISBN 9780073191461.
6. Levelt, Willem JM (2008). Introducción a la teoría de lenguajes formales y autómatas. John Benjamins Publishing. pág. 26. ISBN 978-90-272-3250-2.
7. Davis, Martin ; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica (2.ª ed.). Morgan Kaufmann. págs. 330–331. ISBN 978-0-08-050246-5.
8. Chomsky, N. (1963). "Propiedades formales de la gramática". En Luce, RD; Bush, RR; Galanter, E. (eds.). Handbook of Mathematical Psychology . Nueva York: Wiley. págs. 360–363.
9. Levelt, Willem JM (2008). Introducción a la teoría de lenguajes formales y autómatas. John Benjamins Publishing. pp. 125–126. ISBN 978-90-272-3250-2.
10. Carlos Martín Vide, ed. (1999). Issues in Mathematical Linguistics: Workshop on Mathematical Linguistics, State College, Pa., abril de 1998. John Benjamins Publishing. pp. 186–187. ISBN 90-272-1556-1.
11. Zhang, Da-Qian, Kang Zhang y Jiannong Cao. "Un formalismo gramatical de grafos sensible al contexto para la especificación de lenguajes visuales". The Computer Journal 44.3 (2001): 186–200.
12. Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 9780201029888.; p. 223–224; Ejercicio 9, p. 230. En la edición de 2003 se ha omitido el capítulo sobre los CSG.
13. Hazewinkel, Michiel (1989). Enciclopedia de Matemáticas. vol. 4. Medios científicos y comerciales de Springer. pag. 297.ISBN​ 978-1-55608-003-6.También en https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive
14. Ito, Masami; Kobayashi, Yuji; Shoji, Kunitaka (2010). Autómatas, lenguajes formales y sistemas algebraicos: actas de AFLAS 2008, Kioto, Japón, 20 a 22 de septiembre de 2008. World Scientific. pag. 183.ISBN​ 978-981-4317-60-3.citando a Penttonen, Martti (agosto de 1974). "Contexto unilateral y bilateral en gramáticas formales". Información y Control . 25 (4): 371–392. doi : 10.1016/S0019-9958(74)91049-3 .
15. Obtuvieron la gramática mediante la transformación sistemática de una gramática sin restricciones , dada en el Ejemplo 9.4, a saber:
    1. ${\displaystyle S\rightarrow ACaB}$,
    2. ${\displaystyle Ca\rightarrow aaC}$,
    3. ${\displaystyle CB\rightarrow DB}$,
    4. ${\displaystyle CB\rightarrow E}$,
    5. ${\displaystyle aD\rightarrow Da}$,
    6. ${\displaystyle AD\rightarrow AC}$,
    7. ${\displaystyle aE\rightarrow Ea}$,
    8. ${\displaystyle AE\rightarrow \varepsilon }$.
    En la gramática sensible al contexto, una cadena encerrada entre corchetes, como , se considera un símbolo único (similar a p. ej. en la forma Backus–Naur ). Los nombres de los símbolos se eligen para que se asemejen a la gramática sin restricciones. Del mismo modo, los grupos de reglas en la gramática sensible al contexto se numeran según la regla de gramática sin restricciones de la que se originaron. ${\displaystyle [ACaB]}$<name-part>
16. Kuroda, Sige-Yuki (junio de 1964). "Clases de lenguajes y autómatas linealmente acotados". Información y Control . 7 (2): 207–223. doi : 10.1016/s0019-9958(64)90120-2 .
17. Mateescu, Alexandru; Salomaa, Arto (1997). "Capítulo 4: Aspectos de la teoría del lenguaje clásico". en Rozenberg, Grzegorz ; Salomaa, Arto (eds.). Manual de lenguajes formales. Tomo I: Palabra, lengua, gramática . Springer-Verlag. págs. 175-252. ISBN 3-540-61486-9., Aquí: Teorema 2.2, pág. 190
18. (Hopcroft, Ullman, 1979); Teorema 9.5, 9.6, págs. 225-226
19. Sutner, Klaus (primavera de 2016). "Gramáticas sensibles al contexto" (PDF) . Universidad Carnegie Mellon . Archivado desde el original (PDF) el 2017-02-03 . Consultado el 2019-08-29 .
20. PS Landweber (1963). "Tres teoremas sobre gramáticas de estructura sintagmática de tipo 1". Información y control . 6 (2): 131–136. doi : 10.1016/s0019-9958(63)90169-4 .
21. Meduna, Alexander (2000). Autómatas y lenguajes: teoría y aplicaciones. Springer Science & Business Media. pág. 755. ISBN 978-1-85233-074-3.
22. Levelt, Willem JM (2008). Introducción a la teoría de lenguajes formales y autómatas. John Benjamins Publishing. pp. 126-127. ISBN 978-90-272-3250-2.
23. Martin, John C. (2010). Introducción a los lenguajes y la teoría de la computación (4.ª ed.). Nueva York, NY: McGraw-Hill. pág. 283. ISBN 9780073191461.
24. (Hopcroft, Ullman, 1979); Ejercicio S9.10, pág. 230-231
25. (Hopcroft, Ullman, 1979); Ejercicio S9.14, pág. 230–232. h asigna cada símbolo a sí mismo o a la cadena vacía.
26. Un ejemplo de una gramática de este tipo, diseñada para resolver el problema QSAT , se da en Lita, CV (01-09-2016). "On Complexity of the Detection Problem for Bounded Length Polymorphic Viruses". 2016 18th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC) . pp. 371–378. doi :10.1109/SYNASC.2016.064. ISBN 978-1-5090-5707-8.S2CID 18067130  .
27. (Hopcroft, Ullman, 1979); Ejercicio S9.13, pág. 230-231
28. Kallmeyer, Laura (2011). "Formalismos gramaticales ligeramente sensibles al contexto: los lenguajes naturales no son independientes del contexto" (PDF) . Archivado (PDF) desde el original el 19 de agosto de 2014.
29. Kallmeyer, Laura (2011). "Formalismos gramaticales ligeramente sensibles al contexto: sistemas de reescritura lineales libres de contexto" (PDF) . Archivado (PDF) desde el original el 19 de agosto de 2014.
30. Kallmeyer, Laura (2010). Análisis sintáctico más allá de las gramáticas libres de contexto . Springer Science & Business Media. págs. 1–5. ISBN 978-3-642-14846-0.

Lectura adicional

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

Enlaces externos

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