Hispanopedia Wiki
Articulo de referencia

Gramática no contractiva

En la teoría del lenguaje formal , una gramática no contractiva (también llamada gramática monótona ) es un tipo de gramática formal cuyas reglas de producción nunca disminuyen ...

Hispanopedia WikiContenido en espanolLectura gratuita

En la teoría del lenguaje formal , una gramática no contractiva (también llamada gramática monótona ) es un tipo de gramática formal cuyas reglas de producción nunca disminuyen la longitud total de una cadena durante la derivación . Esto significa que, al aplicar cualquier regla para transformar una cadena en otra, la cadena resultante debe tener al menos tantos símbolos como la original.

Las gramáticas no contractivas son importantes porque son equivalentes en poder expresivo a las gramáticas sensibles al contexto y definen la misma clase de lenguajes (los lenguajes sensibles al contexto ) en la jerarquía de Chomsky . Esta equivalencia las hace importantes para comprender los límites computacionales del procesamiento del lenguaje natural y el diseño de compiladores , ya que pueden modelar fenómenos lingüísticos complejos manteniendo ciertas propiedades matemáticas deseables. Algunos autores utilizan el término gramática sensible al contexto para referirse a las gramáticas no contractivas en general, aunque este uso varía en la literatura. [ 1 ]

Un concepto estrechamente relacionado es la gramática esencialmente no contractiva , que permite una excepción especial: una regla que produce la cadena vacía a partir del símbolo inicial , siempre que el símbolo inicial nunca aparezca en ninguna otra parte de la gramática.

Definiciones formales

Una gramática es no contractiva si para todas sus reglas de producción, α  →  β (donde α y β son cadenas de símbolos no terminales y terminales), se cumple que |α| ≤ |β|, es decir, β tiene al menos tantos símbolos como α.

Una gramática es esencialmente no contractiva si puede haber una excepción, a saber, una regla S → ε donde S es el símbolo inicial y ε la cadena vacía , y además, S nunca aparece en el lado derecho de ninguna regla.

Una gramática sensible al contexto es una gramática no contractiva en la que todas las reglas tienen la forma αAβ  →  αγβ, donde A es un no terminal y γ es una cadena no vacía de símbolos no terminales y/o terminales. Sin embargo, algunos autores utilizan el término gramática sensible al contexto para referirse a las gramáticas no contractivas en general. [ 1 ]

Una gramática no contractiva en la que |α| < |β| para todas las reglas se denomina gramática creciente sensible al contexto .

Historia

Chomsky (1959) introdujo la jerarquía de Chomsky , en la que las gramáticas sensibles al contexto aparecen como gramáticas de "tipo 1"; las gramáticas generales no contractivas no aparecen. [ 2 ]

Chomsky (1963) llama a una gramática no contractiva una "gramática de tipo 1" y a una gramática sensible al contexto una "gramática de tipo 2", y al presentar una conversión de la primera a la segunda, demuestra que ambas son débilmente equivalentes . [ 3 ]

Kuroda (1964) introdujo la forma normal de Kuroda, en la que se pueden convertir todas las gramáticas no contractivas. [ 4 ]

Ejemplo

Esta gramática, con el símbolo inicial S , genera el lenguaje { a n b n c n  : n ≥ 1 } , [ 5 ] que no es libre de contexto debido al lema de bombeo .

A continuación se muestra una gramática sensible al contexto para el mismo idioma .

Poder expresivo

Toda gramática sensible al contexto es una gramática no contractiva.

Existen procedimientos sencillos para

Por lo tanto, estos tres tipos de gramática son iguales en poder expresivo, ya que todos describen exactamente los lenguajes sensibles al contexto que no incluyen la cadena vacía; las gramáticas esencialmente no contractivas describen exactamente el conjunto de lenguajes sensibles al contexto .

Una conversión directa

Una conversión directa a gramáticas sensibles al contexto, evitando la forma normal de Kuroda:

Para una gramática no contractiva arbitraria ( N , Σ, P , S ), construya la gramática sensible al contexto ( N ', Σ, P ', S ) de la siguiente manera:

  1. Para cada símbolo terminal a ∈ Σ, introduzca un nuevo símbolo no terminal [ a ] ​​∈ N ', y una nueva regla ([ a ] ​​→ a ) ∈ P '.
  2. En las reglas de P , reemplace cada símbolo terminal a por su correspondiente símbolo no terminal [ a ]. Como resultado, todas estas reglas tienen la forma X 1 ... X m → Y 1 ... Y n para no terminales X i , Y j y m ≤ n .
  3. Reemplazar cada regla X 1 ... X m → Y 1 ... Y n con m >1 por 2 m reglas: [ nota 1 ]
donde cada Z i ∈ N ' es un nuevo no terminal que no aparece en ningún otro lugar. [ 7 ] [ 8 ]

Por ejemplo, la gramática no contractiva anterior para { a n b n c n | n ≥ 1 } conduce a la siguiente gramática sensible al contexto (con símbolo inicial S ) para el mismo lenguaje:

Véase también

Notas

  1. ↑ Para mayor comodidad, la parte que no corresponde al contexto, tanto del lado izquierdo como del derecho, se muestra en negrita.

Referencias

  1. 1 2 Willem JM Levelt (2008). Introducción a la teoría de los lenguajes formales y los autómatas . John Benjamins Publishing. págs. 125–126 . ISBN  978-90-272-3250-2.
  2. ↑ Chomsky, N. 1959a. Sobre ciertas propiedades formales de las gramáticas. Information and Control 2: 137–67. (141–42 para las definiciones)
  3. ↑ Noam Chomsky (1963). «Propiedades formales de la gramática». En RD Luce, RR Bush y E. Galanter (eds.). Manual de psicología matemática . Vol. II. Nueva York: Wiley. págs. 323-418 .  Aquí: págs. 360–363 y 367
  4. 1 2 Sige-Yuki Kuroda (junio de 1964). "Clases de lenguajes y autómatas linealmente acotados" . Information and Control . 7 (2): 207– 223. doi : 10.1016/s0019-9958(64)90120-2 .
  5. ↑ Mateescu y Salomaa (1997) , Ejemplo 2.1, p. 188
  6. ^ Mateescu y Salomaa (1997) , Teorema 2.2, p. 190
  7. ^ Mateescu y Salomaa (1997) , Teorema 2.1, p. 187
  8. ↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. ISBN 0-201-02988-X.Ejercicio 9.9, pág. 230. En la edición de 2003, se omitió el capítulo sobre lenguas no contractivas/sensibles al contexto.
  • Book, RV (1973). "Sobre la estructura de las gramáticas sensibles al contexto". International Journal of Computer & Information Sciences . 2 (2): 129– 139. doi : 10.1007/BF00976059 . hdl : 2060/19710024701 . S2CID 31699138 . 
  • 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 a 252. ISBN  3-540-61486-9.