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 colocan 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 contractiva o un autómata lineal limitado , se denomina lenguaje sensible al contexto . En realidad, algunos libros de texto definen a los CSG como no contractuales, [2] [3] [4] [5] aunque no es así como Noam Chomsky los definió en 1959. [6] [7] 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 hace una diferencia en términos de qué gramáticas se consideran estructuralmente sensibles al contexto; este último tema fue analizado 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" como engañosa y ha propuesto que "no borrado" explica 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, es una pregunta abierta cuánto del poder expresivo de 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 sensibles al contexto levemente más manejables desde el punto de vista computacional . [ cita requerida ] Las sintaxis de algunos lenguajes de programación visual se pueden describir mediante gramáticas de gráficos sensibles al contexto . [11]
Definicion 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 sensible al contexto si todas las reglas en P son de la forma
- α A β → αγβ
con A ∈ N , [nota 1] α, β ∈ ( N ∪Σ) * [nota 2] y γ ∈ ( N ∪Σ) + . [nota 3]
Una cadena u ∈ ( N ∪Σ) * produce directamente , o deriva directamente a , una cadena v ∈ ( N ∪Σ) * , denotada como u ⇒ v , si u puede escribirse como l α A β r , y v puede escribirse como l αγβ r , para alguna regla de producción (α A β → αγβ) ∈ P , y algunas cadenas de contexto l , r ∈ ( N ∪Σ) * . De manera más general, se dice que u cede , o deriva a , v , denotado como u ⇒ * v , si u = u 1 ⇒ ... ⇒ u n = v para algunos n ≥0 y algunas cadenas u 2 , ... , u n -1 ( N ∪Σ) * . Es decir, la relación (⇒ * ) es el cierre transitivo reflexivo 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 de inicio, formalmente: L ( G ) = { w ∈ Σ * : S ⇒ * w }. Las derivaciones que no terminan en una cadena compuesta por símbolos terminales solo son posibles, pero no contribuyen a L ( G ).
La única diferencia entre esta definición de Chomsky y la de gramáticas no restringidas es que γ puede estar vacío en el caso no restringido. [10]
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 , [12 ] ver Gramática sin contracciones # Transformación en gramática sensible al contexto .
Además, una regla de la forma
- S → λ
donde λ representa la cadena vacía y S no aparece en el lado derecho de ninguna regla está permitido. La adición de la cadena vacía permite la declaración de que los lenguajes sensibles al contexto son un superconjunto adecuado de los lenguajes libres de contexto, en lugar de tener que hacer la declaració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 el α y el β 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 en la que no se tiene en cuenta el contexto de un no terminal. De hecho, toda producción de una gramática libre de contexto tiene la forma V → w donde V es un solo 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 contractuales (que nunca pueden incluir la cadena vacía), entonces los idiomas en estas dos definiciones son idénticos.
El contexto izquierda - y derecho de contexto gramáticas -sensibles se definen mediante la restricción de las reglas para sólo la forma α A → αγ y sólo 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 de
La siguiente gramática sensible al contexto, con el símbolo de inicio S , genera el lenguaje canónico no libre de contexto { a n b n c n : 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 |
Reglas 1 y 2 permiten para el soplado-up S a un n 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 β → αγβ); reglas 7-10 permiten la sustitución de un no terminales B y C , con sus correspondientes terminales b y c respectivamente, siempre que esté en el lugar correcto. Una cadena de generación para aaabbbccc es:
- S
- → 2 aSBC
- → 2 a aSBC BC
- → 1 aa aBC BCBC
- → 3 aaaB CZ CBC
- → 4 aaaB WZ CBC
- → 5 aaaB WC CBC
- → 6 aaaB BC CBC
- → 3 aaaBBC CZ C
- → 4 aaaBBC WZ C
- → 5 aaaBBC WC C
- → 6 aaaBBC BC C
- → 3 aaaBB CZ CC
- → 4 aaaBB WZ CC
- → 5 aaaBB WC CC
- → 6 aaaBB BC CC
- → 7 aa ab BBCCC
- → 8 aaa bb BCCC
- → 8 aaab bb CCC
- → 9 aaabb bc CC
- → 10 aaabbb cc C
- → 10 aaabbbc cc
Gramáticas más complicadas se puede utilizar para analizar { a n b n c n d n : n ≥ 1} y otros idiomas con incluso más letras. Aquí mostramos un enfoque más simple utilizando gramáticas no contractuales: comience con un núcleo de producciones regulares que generen las formas oracionales y luego incluir las producciones no contractuales , , , , , , , , , .
Una gramática no contractual (para la que hay un equivalente ) para el idioma es definido por y , , , , , , .
Con estas definiciones, una derivación de es: . [ cita requerida ]
En el ejemplo 9.5 (p. 224) de (Hopcroft, Ullman, 1979) se construye una gramática sin contracciones para el lenguaje { a 2 i : i ≥ 1}: [15]
Forma normal de Kuroda
Cada gramática sensible al contexto que no genera la cadena vacía se puede transformar en una débilmente equivalente en la forma normal de Kuroda . "Débilmente equivalente" aquí significa que las dos gramáticas generan el mismo idioma. En general, la forma normal no será sensible al contexto, pero será una gramática sin contracciones . [16] [17]
La forma normal de Kuroda es una forma normal real para gramáticas que no se contraen.
Propiedades y usos
Equivalencia a un autómata acotado lineal
Un lenguaje formal puede describirse mediante una gramática sensible al contexto si y solo si es aceptado por algún autómata acotado lineal (LBA). [18] En algunos libros de texto, este resultado se atribuye únicamente a Landweber y Kuroda . [7] Otros lo llaman el 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. Kuroda introdujo la noción de LBA no determinista y la equivalencia entre LBA y CSG en 1964. [20] [21] )
A partir de 2010[actualizar]Todavía es una pregunta abierta si cada lenguaje sensible al contexto puede ser aceptado por un LBA determinista . [22]
Propiedades de cierre
Los lenguajes sensibles al contexto se cierran 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 . [23]
Cada lenguaje L recursivamente enumerable puede escribirse como h ( L ) para algún lenguaje L sensible al contexto y algún homomorfismo de cadena h . [24]
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, existen gramáticas sensibles al contexto cuyos lenguajes son completos con PSPACE. En otras palabras, existe 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). [25]
El problema de la vacuidad para las gramáticas sensibles al contexto (dada una gramática sensible al contexto G , es L ( G ) = ∅?) Es indecidible . [26] [nota 5]
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 R recursivamente enumerable , existe un lenguaje / gramática G sensible al contexto 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 sólo si existe un número entero positivo n para el que sc n está en G, donde c es un símbolo arbitrario no es parte de R . [10]
Se ha demostrado que casi todos los lenguajes naturales pueden caracterizarse en general 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 antes mencionado para los 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 los fenómenos de codificación ilimitada . 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 los lenguajes naturales. Por ejemplo, los sistemas de reescritura lineal sin contexto (LCFRS) estrictamente más débiles (que CSG ) pueden explicar el fenómeno de las dependencias entre series; se puede escribir una gramática LCFRS para { a n b n c n d n | n ≥ 1} por ejemplo. [27] [28] [29]
La investigación en curso en la lingüística computacional se ha centrado en la formulación de otras clases de idiomas que son " moderadamente sensibles al contexto ", cuyos problemas de decisión son factibles, tales como gramáticas-contiguo de árboles , gramáticas categoriales combinatorias , junto lenguajes libres de contexto , y reescritura libre de contexto lineal sistemas . 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 ha identificado con gramáticas de concatenación de rango , que ahora se consideran las más expresivas de los lenguajes sensibles al contexto leve. [29]
Ver también
- Jerarquía de Chomsky
- Creciente gramática sensible al contexto
- Gramática de cláusulas definidas # Gramáticas sin contexto
- Lista de generadores de analizadores sintácticos para gramáticas sensibles al contexto
Notas
- ^ es decir, A un solo no terminal
- ^ es decir, cadenas α y β de no terminales y terminales
- ^ es decir, γ es una cadena no vacía de no terminales y terminales
- ^ más formalmente: si L ⊆ Σ * es un lenguaje sensible al contexto y f mapea cada a ∈Σ a un lenguaje sensible al contexto f ( a ), el f ( L ) es nuevamente un lenguaje sensible al contexto
- ^ 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 está cerrado en la intersección , pero (3) que la desunión de los lenguajes libres de contexto es indecidible .
Referencias
- ^ (Hopcroft, Ullman, 1979); Sección 9.4, p.227
- ^ Linz, Peter (2011). Introducción a los lenguajes formales y los autómatas . Editores Jones & Bartlett. pag. 291. ISBN 978-1-4496-1552-9.
- ^ Meduna, Alexander (2000). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. pag. 730. ISBN 978-1-85233-074-3.
- ^ Davis, Martin ; Sigal, Ron; Weyuker, Elaine J. (1994). Computabilidad, complejidad y lenguajes: fundamentos de la informática teórica (2ª ed.). Morgan Kaufmann. pag. 189. ISBN 978-0-08-050246-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. pag. 277. ISBN 9780073191461.
- ^ Levelt, Willem JM (2008). Introducción a la teoría de lenguajes formales y autómatas . Editorial John Benjamins. pag. 26. ISBN 978-90-272-3250-2.
- ^ a b 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.
- ^ 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.
- ^ Levelt, Willem JM (2008). Introducción a la teoría de lenguajes formales y autómatas . Editorial John Benjamins. págs. 125-126. ISBN 978-90-272-3250-2.
- ^ a b c Carlos Martín Vide, ed. (1999). Issues in Mathematical Linguistics: Workshop on Mathematical Linguistics, State College, Pa., Abril de 1998 . Editorial John Benjamins. págs. 186-187. ISBN 90-272-1556-1.
- ^ 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.
- ^ Hopcroft, John E .; Ullman, Jeffrey D. (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley.; pag. 223–224; Ejercicio 9, pág. 230. En la edición de 2003, se omitió el capítulo sobre CSG.
- ^ Hazewinkel, Michiel (1989). Enciclopedia de Matemáticas . 4 . Springer Science & Business Media. pag. 297. ISBN 978-1-55608-003-6.también en https://www.encyclopediaofmath.org/index.php/Grammar,_context-sensitive
- ^ Ito, Masami; Kobayashi, Yuji; Shoji, Kunitaka (2010). Autómatas, lenguajes formales y sistemas algebraicos: Actas de AFLAS 2008, Kyoto, Japón, 20-22 de septiembre de 2008 . World Scientific. pag. 183. ISBN 978-981-4317-60-3. citando 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 .
- ↑ Obtuvieron la gramática por transformación sistemática de una gramática irrestricta , dada en Exm. 9,4, a saber:
- ,
- ,
- ,
- ,
- ,
- ,
- ,
- .
en la forma Backus-Naur ). Los nombres de los símbolos se eligen para parecerse a la gramática no restringida. Del mismo modo, los grupos de reglas en la gramática sensible al contexto están numerados por la regla de gramática no restringida de la que se originaron. - ^ 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 .
- ^ 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. Volumen I: Palabra, lenguaje, gramática . Springer-Verlag. págs. 175–252. ISBN 3-540-61486-9., Aquí: Teorema 2.2, p. 190
- ^ (Hopcroft, Ullman, 1979); Teorema 9.5, 9.6, pág. 225–226
- ^ a b https://www.cs.cmu.edu/~flac/pdf/ContSens.pdf
- ^ Meduna, Alexander (2000). Autómatas y lenguajes: teoría y aplicaciones . Springer Science & Business Media. pag. 755. ISBN 978-1-85233-074-3.
- ^ Levelt, Willem JM (2008). Introducción a la teoría de lenguajes formales y autómatas . Editorial John Benjamins. págs. 126-127. ISBN 978-90-272-3250-2.
- ^ Martin, John C. (2010). Introducción a los lenguajes y la teoría de la computación (4ª ed.). Nueva York, NY: McGraw-Hill. pag. 283. ISBN 9780073191461.
- ^ (Hopcroft, Ullman, 1979); Ejercicio S9.10, p. 230–231
- ^ (Hopcroft, Ullman, 1979); Ejercicio S9.14, p. 230–232. h asigna cada símbolo a sí mismo o a la cadena vacía.
- ^ Un ejemplo de tal gramática, diseñado para resolver elproblema QSAT , se da en Lita, CV (1 de septiembre de 2016). "Sobre la complejidad del problema de detección de virus polimórficos de longitud limitada". 2016 18º Simposio Internacional sobre Algoritmos Simbólicos y Numéricos para Computación Científica (SYNASC) : 371–378. doi : 10.1109 / SYNASC.2016.064 . ISBN 978-1-5090-5707-8.
- ^ (Hopcroft, Ullman, 1979); Ejercicio S9.13, p. 230–231
- ^ Kallmeyer, Laura (2011). "Formalismos gramaticales ligeramente sensibles al contexto: los lenguajes naturales no están libres de contexto" (PDF) .
- ^ Kallmeyer, Laura (2011). "Formalismos gramaticales ligeramente sensibles al contexto: sistemas de reescritura lineal sin contexto" (PDF) .
- ^ a b Kallmeyer, Laura (2010). Análisis más allá de las gramáticas libres de contexto . Springer Science & Business Media. págs. 1-5. ISBN 978-3-642-14846-0.
Otras lecturas
- Meduna, Alexander ; Švec, Martin (2005). Gramáticas con condiciones de contexto y sus aplicaciones . John Wiley e hijos. ISBN 978-0-471-73655-4.
enlaces externos
- Análisis de Earley para gramáticas sensibles al contexto