En la teoría del lenguaje formal , una gramática no se contrae (o es monótona ) si todas sus reglas de producción son de la forma α → β donde α y β son cadenas de símbolos no terminales y terminales, y la longitud de α es menor o igual a esa. de β, | α | ≤ | β |, es decir, β no es más corto que α. Una gramática es esencialmente no contractual si puede haber una excepción, a saber, una regla S → ε donde S es el símbolo de inicio y ε la cadena vacía, y además, S nunca aparece en el lado derecho de ninguna regla.
Ninguna de las reglas de una gramática sin contracciones disminuye la longitud de la cadena que se está reescribiendo. Si cada regla aumenta adecuadamente la longitud, la gramática se llama una gramática sensible al contexto en crecimiento .
Historia
Chomsky (1963) llamó a una gramática sin contracciones una gramática de tipo 1 ; en el mismo trabajo, llamó a una gramática sensible al contexto una " gramática de tipo 2", y demostró que estas dos son débilmente equivalentes (las gramáticas libres de contexto fueron designadas como "tipo 4" en este trabajo). [1] El esquema de numeración de tipos en este trabajo de 1963 de Chomsky no coincide con el anterior conocido hoy como la jerarquía de Chomsky porque estaba tratando de enfatizar la distinción entre equivalencia débil [generativa] y fuerte [estructural]; en su trabajo de 1959 había usado "gramática tipo 1" para denotar una gramática sensible al contexto y "tipo 2" para libre de contexto. [2] [3]
Ejemplo
S | → | a B C |
S | → | aSBc |
CB | → | Antes de Cristo |
cama y desayuno | → | cama y desayuno |
Esta gramática, con el símbolo de inicio S , genera el lenguaje { a n b n c n : n ≥ 1} , [4] que no está libre de contexto debido al lema de bombeo .
A continuación se muestra una gramática sensible al contexto para el mismo idioma .
Transformarse en gramática sensible al contexto
Cada gramática no contractual ( N , Σ, P , S ) se puede transformar en una gramática sensible al contexto ( N ', Σ, P ', S ) de la siguiente manera:
- Para cada símbolo terminal a ∈ Σ, introduzca un nuevo símbolo no terminal [ a ] ∈ N 'y una nueva regla ([ a ] → a ) ∈ P '.
- En las reglas de P , reemplace cada símbolo terminal a por su símbolo no terminal correspondiente [ a ]. Como resultado, todas estas reglas son de la forma X 1 ... X m → Y 1 ... Y n para los no terminales X i , Y j y m ≤ n .
- Reemplace cada regla X 1 ... X m → Y 1 ... Y n con reglas m > 1 por 2 m : [nota 1]
X 1 X 2 ... X m -1 X m → Z 1 X 2 ... X m -1 X m Z 1 X 2 ... X m -1 X m → Z 1 Z 2 ... X m -1 X m : Z 1 Z 2 ... X m -1 X m → Z 1 Z 2 ... Z m -1 X m Z 1 Z 2 ... Z m -1 X m → Z 1 Z 2 ... Z m -1 Z m Y m +1 ... Y n Z 1 Z 2 ... Z m -1 Z m Y m +1 ... Y n → Y 1 Z 2 ... Z m -1 Z m Y m +1 ... Y n Y 1 Z 2 ... Z m -1 Z m Y m +1 ... Y n → Y 1 Y 2 ... Z m -1 Z m Y m +1 ... Y n : Y 1 Y 2 ... Z m -1 Z m Y m +1 ... Y n → Y 1 Y 2 ... Y m -1 Z m Y m +1 ... Y n Y 1 Y 2 ... Y m -1 Z m Y m +1 ... Y n → Y 1 Y 2 ... Y m -1 Y m Y m +1 ... Y n
Por ejemplo, la gramática no contractual anterior para { a n b n c n | n ≥ 1} conduce a la siguiente gramática sensible al contexto (con el símbolo de inicio S ) para el mismo idioma:
[ a ] | → | a | desde el paso 1 | ||||
[ b ] | → | B | desde el paso 1 | ||||
[ c ] | → | C | desde el paso 1 | ||||
S | → | [ a ] | [ b ] | [ c ] | desde el paso 2, sin cambios | ||
S | → | [ a ] | S | B | [ c ] | desde el paso 2, sin cambios | |
del paso 2, modificado más abajo | |||||||
[ c ] | B | → | Z 1 | B | modificado desde arriba en el paso 3 | ||
Z 1 | B | → | Z 1 | Z 2 | modificado desde arriba en el paso 3 | ||
Z 1 | Z 2 | → | B | Z 2 | modificado desde arriba en el paso 3 | ||
B | Z 2 | → | B | [ c ] | modificado desde arriba en el paso 3 | ||
del paso 2, modificado más abajo | |||||||
[ b ] | B | → | Z 3 | B | modificado desde arriba en el paso 3 | ||
Z 3 | B | → | Z 3 | Z 4 | modificado desde arriba en el paso 3 | ||
Z 3 | Z 4 | → | [ b ] | Z 4 | modificado desde arriba en el paso 3 | ||
[ b ] | Z 4 | → | [ b ] | [ b ] | modificado desde arriba en el paso 3 |
Poder expresivo
De manera similar, existe un procedimiento sencillo para llevar cualquier gramática no contraída a la forma normal de Kuroda . [7] [8] Viceversa, cada gramática sensible al contexto y cada gramática de forma normal de Kuroda es trivialmente también una gramática sin contracciones. Por lo tanto, las gramáticas que no se contraen, las gramáticas en la forma normal de Kuroda y las gramáticas sensibles al contexto tienen el mismo poder expresivo. Para ser precisos, las gramáticas sin contracciones describen exactamente los lenguajes sensibles al contexto que no incluyen la cadena vacía, mientras que las gramáticas esencialmente sin contracciones describen exactamente el conjunto de lenguajes sensibles al contexto .
Ver también
Notas
- ^ Por conveniencia, la parte sin contexto del lado izquierdo y derecho se muestra en negrita.
Referencias
- ^ Noam Chomsky (1963). "Propiedades formales de la gramática". En RD Luce y RR Bush y E. Galanter (ed.). Manual de Psicología Matemática . II . Nueva York: Wiley. págs. 323 –418. Aquí: págs. 360–363 y 367
- ^ Chomsky, N. 1959a. Sobre ciertas propiedades formales de las gramáticas. Información y control 2: 137–67. (141–42 para las definiciones)
- ^ Willem JM Levelt (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.
- ^ Mateescu y Salomaa (1997) , ejemplo 2.1, p. 188
- ^ Mateescu y Salomaa (1997) , Teorema 2.1, p. 187
- ^ John E. Hopcroft, Jeffrey D. Ullman (1979). Introducción a la teoría, los lenguajes y la computación de los autómatas . Addison-Wesley. ISBN 0-201-02988-X.Ejercicio 9.9, p.230. En la edición de 2003, se omitió el capítulo sobre lenguajes sensibles al contexto / no contractuales.
- ^ Sige-Yuki Kuroda (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 y Salomaa (1997) , Teorema 2.2, p. 190
- Libro, RV (1973). "Sobre la estructura de gramáticas sensibles al contexto". Revista Internacional de Ciencias de la Información y la Computación . 2 (2): 129-139. doi : 10.1007 / BF00976059 . hdl : 2060/19710024701 .
- 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.