Los lenguajes indexados son una clase de lenguajes formales descubiertos por Alfred Aho ; [1] se describen mediante gramáticas indexadas y pueden ser reconocidos por autómatas de pila anidados . [2]
Los lenguajes indexados son un subconjunto adecuado de lenguajes sensibles al contexto . [1] Califican como una familia abstracta de lenguajes (además, un AFL completo) y por lo tanto satisfacen muchas propiedades de cierre. Sin embargo, no están cerrados por intersección o complemento. [1]
La clase de lenguajes indexados tiene importancia práctica en el procesamiento del lenguaje natural como una generalización computacionalmente asequible [ cita requerida ] de los lenguajes libres de contexto , ya que las gramáticas indexadas pueden describir muchas de las restricciones no locales que ocurren en los lenguajes naturales.
Gerald Gazdar (1988) [3] y Vijay-Shanker (1987) [4] introdujeron una clase de lenguaje levemente sensible al contexto ahora conocida como gramáticas indexadas lineales (LIG). [5] Las gramáticas indexadas lineales tienen restricciones adicionales relativas a IG. Los LIG son débilmente equivalentes (generan la misma clase de idioma) que las gramáticas adyacentes al árbol . [6]
Ejemplos de
Los siguientes idiomas están indexados, pero no están libres de contexto :
Estos dos idiomas también están indexados, pero ni siquiera son levemente sensibles al contexto según la caracterización de Gazdar:
Por otro lado, el siguiente idioma no está indexado: [7]
Propiedades
Hopcroft y Ullman tienden a considerar los lenguajes indexados como una clase "natural", ya que son generados por varios formalismos, como: [9]
- Aho 's gramáticas indexadas [1]
- Autómatas de pila anidados unidireccionales de Aho [10]
- Macro gramáticas de Fischer [11]
- Autómatas de Greibach con pilas de pilas [12]
- Caracterización algebraica de Maibaum [13]
Hayashi [14] generalizó el lema de bombeo a gramáticas indexadas. A la inversa, Gilman [7] da un "lema que se encoge" para los lenguajes indexados.
Ver también
- Jerarquía de Chomsky
- Gramática indexada
- Lenguaje ligeramente sensible al contexto
Referencias
- ↑ a b c d Aho, Alfred (1968). "Gramáticas indexadas: una extensión de las gramáticas libres de contexto". Revista de la ACM . 15 (4): 647–671. doi : 10.1145 / 321479.321488 . S2CID 9539666 .
- ^ a b c Partee, Barbara ; ter Meulen, Alice ; Wall, Robert E. (1990). Métodos matemáticos en lingüística . Editores académicos de Kluwer. págs. 536–542. ISBN 978-90-277-2245-4.
- ^ a b c Gazdar, Gerald (1988). "Aplicabilidad de las gramáticas indexadas a los lenguajes naturales". En Reyle, U .; Rohrer, C. (eds.). Análisis del lenguaje natural y teorías lingüísticas . Estudios de Lingüística y Filosofía. 35 . Springer Holanda. págs. 69–94. doi : 10.1007 / 978-94-009-1337-0_3 . ISBN 978-94-009-1337-0.
- ^ Vijayashanker, K. (1987). Un estudio de gramáticas adyacentes a árboles (Tesis). ProQuest 303610666 .
- ^ Kallmeyer, Laura (2010). Análisis más allá de las gramáticas libres de contexto . Saltador. pag. 31. ISBN 978-3-642-14846-0.
- ^ Kallmeyer, Laura (16 de agosto de 2010). Análisis más allá de las gramáticas libres de contexto . Saltador. pag. 32. ISBN 978-3-642-14846-0.
- ^ a b Gilman, Robert H. (1996). "Un lema que se encoge para los lenguajes indexados". Informática Teórica . 163 (1–2): 277–281. arXiv : matemáticas / 9509205 . doi : 10.1016 / 0304-3975 (96) 00244-7 . S2CID 14479068 .
- ^ Hopcroft, John ; Ullman, Jeffrey (1979). Introducción a la teoría de autómatas, lenguajes y computación . Addison-Wesley. pag. 390. ISBN 978-0-201-02988-8.
- ^ Introducción a la teoría de autómatas, lenguajes y computación, [8] Notas bibliográficas, p.394-395
- ^ Aho, Alfred V. (julio de 1969). "Autómatas de pila anidada". Revista de la ACM . 16 (3): 383–406. doi : 10.1145 / 321526.321529 . S2CID 685569 .
- ^ Fischer, Michael J. (octubre de 1968). Gramáticas con producciones tipo macro . Noveno Simposio Anual sobre Teoría de la Conmutación y Autómatas (SWAT 1968). págs. 131-142. doi : 10.1109 / SWAT.1968.12 .
- ^ Greibach, Sheila A. (marzo de 1970). "AFL completos y sustitución iterada anidada" . Información y control . 16 (1): 7–35. doi : 10.1016 / s0019-9958 (70) 80039-0 .
- ^ Maibaum, TSE (junio de 1974). "Un enfoque generalizado de los lenguajes formales" . Revista de Ciencias de la Computación y Sistemas . 8 (3): 409–439. doi : 10.1016 / s0022-0000 (74) 80031-0 .
- ^ Hayashi, Takeshi (1973). "En árboles de derivación de gramáticas indexadas: una extensión del {$ uvwxy $} - teorema" . Publicaciones del Instituto de Investigaciones en Ciencias Matemáticas . 9 (1): 61–92. doi : 10.2977 / prims / 1195192738 .
enlaces externos
- Capítulo "PNL en Prolog" sobre gramáticas e idiomas indexados