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 un 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 no restringidas . Por lo tanto, los CSG se ubican entre gramáticas libres de contexto y sin restricciones en la jerarquía de Chomsky . ^[1]

Un lenguaje formal que puede describirse 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 definen los CSG como no contractuales, ^{[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í marca la 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 ocurre que una palabra puede ser apropiada o no en un lugar determinado dependiendo del contexto. Walter Savitch ha criticado la terminología "sensible al contexto" por considerarla engañosa y propuso "no borrar" para explicar mejor la distinción entre un 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 están libres de contexto, queda abierta la pregunta de cuánto poder expresivo de los CSG se necesita para capturar la sensibilidad contextual que se encuentra en los lenguajes naturales. La investigación posterior en esta área se ha centrado en los lenguajes más manejables computacionalmente y ligeramente sensibles al contexto . ^{[ cita necesaria ]} Las sintaxis de algunos lenguajes de programación visual se pueden describir mediante gramáticas gráficas sensibles al contexto . ^[11]

Definicion formal

Gramática formal

Notemos 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 inicial. ${\displaystyle G=(N,\Sigma ,P,S)}$ ${\displaystyle N}$ ${\displaystyle \Sigma }$ ${\displaystyle P}$ ${\displaystyle S\in N}$

Una cadena produce o deriva directamente de una cadena , denotada como , si v puede obtenerse de u mediante la aplicación de alguna regla de producción en P , es decir, si y , donde es una regla de producción y es la izquierda no afectada y parte derecha de la cuerda, respectivamente. De manera más general, se dice que u produce o deriva a v , denotado 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 de su símbolo inicial, formalmente: . Las derivaciones que no terminan en una cadena compuesta únicamente de 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 está la cadena vacía o la forma ${\displaystyle S\to \varepsilon }$ ${\displaystyle \varepsilon }$

α A β → αγβ

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 sensible al contexto se explica por α y β que forman el contexto de A y determinan si A puede reemplazarse con γ 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 poder a las gramáticas sin restricciones . ^[10]

Definiciones (débilmente) equivalentes

Una gramática no contractual 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 a la longitud de v .

Toda gramática sensible al contexto no es contractual, mientras que toda gramática no contractual se puede convertir 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 gramáticas no contractuales en general.

Las gramáticas sensibles al contexto izquierdo y al contexto derecho se definen restringiendo las reglas solo a la forma α A → αγ y solo a 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 la forma normal de Penttonen . ^[14]

Ejemplos

a n b n c n

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

Las reglas 1 y 2 permiten ampliar S a 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 terminal B o C no terminal con su correspondiente terminal b o c , respectivamente, siempre que esté en el lugar correcto. Una cadena de generación para aaabbcccc es:

S

→ ₂ aSBC

→ ₂ a aSBC BC

→ ₁ aa aBC BCBC

→ ₃ aaaB CZ CBC

→ ₄ aaaB WZ CBC

→ ₅ aaaB WC CBC

→ ₆ aaaB BC CBC

→ ₃ aaaBBC CZ C

→ ₄ aaaBBC WZ C

→ ₅ aaaBBC WC C

→ ₆ aaaBBC BC C

→ ₃ aaaBB CZ CC

→ ₄ aaaBB WZ CC

→ ₅ aaaBB WC CC

→ ₆ aaaBB BC CC

→ ₇ aa ab BBCCC

→ ₈ aaa bb BCCC

→ ₈ aaab bb CCC

→ ₉ aaabb antes de Cristo CC

→ ₁₀ aaabbb cc C

→ ₁₀ aaabbbc cc

a 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 aún más letras. Aquí mostramos un enfoque más simple usando gramáticas sin contracción: ^{[ cita necesaria ]} 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}$

a m b n cm d n​

Una gramática no contractual (para la cual existe un CSG equivalente) para el idioma se define por ${\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 necesaria ]} ${\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}}$

un 2 yo

Una gramática no contractual para el idioma { a ^{2 i} | i ≥ 1 } se construye en el Ejemplo 9.5 (p. 224) de (Hopcroft, Ullman, 1979): ^[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

Cada gramática sensible al contexto que no genera una cadena vacía se puede transformar 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, pero será una gramática no contractual . ^{[16] [17]}

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

Propiedades y usos

Equivalencia al autómata lineal acotado

Un lenguaje formal puede describirse mediante una gramática sensible al contexto si y sólo 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 teorema de 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 de cierre

Los lenguajes sensibles al contexto están cerrados bajo complemento . Este resultado de 1988 se conoce como 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]

Cada lenguaje L recursivamente enumerable se puede escribir como h ( L ) para algún lenguaje L sensible al contexto y algún homomorfismo de cadena h . ^[25]

Problemas computacionales

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

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

Como modelo de lenguajes naturales

Savitch ha demostrado el siguiente resultado teórico, en el que basa su crítica a los CSG como base del lenguaje natural: para cualquier conjunto R recursivamente enumerable , existe un lenguaje/gramática G sensible al contexto que puede usarse como una especie de proxy para probar 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. ^[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 necesaria ]} Peor aún, dado que el problema de decisión antes mencionado para CSG es PSPACE completo, eso los hace totalmente inviables para uso práctico, ya que un algoritmo de tiempo polinomial para un problema PSPACE completo implicaría P = NP .

Se demostró que algunos lenguajes naturales no están libres de contexto, basándose en la identificación de las llamadas dependencias entre series y fenómenos de codificación ilimitada . ^{[ cita necesaria ]} 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 lineal libre de contexto (LCFRS) son estrictamente más débiles que los CSG, pero pueden explicar el 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 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 gramáticas contiguas a árboles , gramáticas categoriales combinatorias , lenguajes acoplados libres de contexto y reescritura lineal libre de contexto. sistemas . Los lenguajes generados por estos formalismos se encuentran propiamente entre los lenguajes libres de contexto y los lenguajes sensibles al contexto.

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

Ver también

• Jerarquía chomsky
• Gramática cada vez más sensible al contexto
• Gramática de cláusula definida # Gramáticas no libres de contexto
• Lista de generadores de analizadores 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 deduce de (1) que los lenguajes libres de contexto también son sensibles al contexto, (2) que el lenguaje sensible al contexto se cierra bajo la intersección, pero (3) la desunión de los lenguajes libres de contexto es indecidible .

Referencias

1. (Hopcroft, Ullman, 1979); Secc.9.4, p.227
2. Linz, Peter (2011). Introducción a los lenguajes formales y los autómatas. Editores Jones y Bartlett. pag. 291.ISBN​ 978-1-4496-1552-9.
3. Meduna, Alejandro (2000). Autómatas y lenguajes: teoría y aplicaciones. Medios de ciencia y negocios de Springer. pag. 730.ISBN​ 978-1-85233-074-3.
4. Davis, Martín ; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica (2ª ed.). Morgan Kaufman. pag. 189.ISBN​ 978-0-08-050246-5.
5. Martín, John C. (2010). Introducción a los lenguajes y la teoría de la computación (4ª ed.). Nueva York, Nueva York: McGraw-Hill. pag. 277.ISBN​ 9780073191461.
6. Nivelado, Willem JM (2008). Introducción a la teoría de los lenguajes formales y los autómatas. Publicación de John Benjamins. pag. 26.ISBN​ 978-90-272-3250-2.
7. Davis, Martín ; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica (2ª ed.). Morgan Kaufman. 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.). Manual de Psicología Matemática . Nueva York: Wiley. págs. 360–363.
9. Nivelado, Willem JM (2008). Introducción a la teoría de los lenguajes formales y los autómatas. Publicación de John Benjamins. págs. 125-126. ISBN 978-90-272-3250-2.
10. Carlos Martín Vide, ed. (1999). Cuestiones de lingüística matemática: taller sobre lingüística matemática, State College, Pensilvania, abril de 1998. John Benjamins Publishing. págs. 186-187. ISBN 90-272-1556-1.
11. Zhang, Da-Qian, Kang Zhang y Jiannong Cao. "Un formalismo gramático gráfico sensible al contexto para la especificación de lenguajes visuales". El diario informático 44.3 (2001): 186–200.
12. Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de autómatas . Addison-Wesley. ISBN 9780201029888.; pag. 223–224; Ejercicio 9, pág. 230. En la edición de 2003, se omitió el capítulo sobre 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 transformación sistemática de una gramática ilimitada , dada en Exm. 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, por ejemplo, en la forma Backus-Naur ). Los nombres de los símbolos se eligen para que se parezcan a la gramática ilimitada. Del mismo modo, los grupos de reglas en la gramática sensible al contexto están numerados según la regla de gramática ilimitada de la que se originaron. ${\displaystyle [ACaB]}$<name-part>
16. Kuroda, Sige-Yuki (junio de 1964). "Clases de lenguajes y autómatas acotados linealmente". 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. 190
18. (Hopcroft, Ullman, 1979); Teorema 9.5, 9.6, pág. 225–226
19. Sutner, Klaus (primavera de 2016). "Gramáticas sensibles al contexto" (PDF) . Universidad de Carnegie mellon . Archivado desde el original (PDF) el 3 de febrero de 2017 . Consultado el 29 de agosto de 2019 .
20. PS Landweber (1963). "Tres teoremas sobre gramáticas de estructura de frases de tipo 1". Información y Control . 6 (2): 131-136. doi : 10.1016/s0019-9958(63)90169-4 .
21. Meduna, Alejandro (2000). Autómatas y lenguajes: teoría y aplicaciones. Medios de ciencia y negocios de Springer. pag. 755.ISBN​ 978-1-85233-074-3.
22. Nivelado, Willem JM (2008). Introducción a la teoría de los lenguajes formales y los autómatas. Publicación de John Benjamins. págs. 126-127. ISBN 978-90-272-3250-2.
23. Martín, John C. (2010). Introducción a los lenguajes y la teoría de la computación (4ª ed.). Nueva York, Nueva York: McGraw-Hill. pag. 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. En Lita, CV (1 de septiembre de 2016) se ofrece un ejemplo de dicha gramática, diseñada para resolver el problema QSAT . "Sobre la complejidad del problema de detección de virus polimórficos de longitud limitada". 2016 XVIII Simposio Internacional sobre Algoritmos Simbólicos y Numéricos para Computación Científica (SYNASC) . págs. 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 están libres de 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 más allá de las gramáticas libres de contexto . Medios de ciencia y negocios de Springer. págs. 1 a 5. ISBN 978-3-642-14846-0.

Otras lecturas

• Meduna, Alejandro ; Švec, Martín (2005). Gramáticas con condiciones de contexto y sus aplicaciones . John Wiley e hijos. ISBN 978-0-471-73655-4.

enlaces externos

• Análisis anticipado de gramáticas sensibles al contexto