Lenguaje indexado

Los lenguajes indexados son una clase de lenguajes formales descubiertos por Alfred Aho ; ^[1] se describen mediante gramáticas indexadas y pueden reconocerse mediante autómatas de pila anidados . ^[2]

Los lenguajes indexados son un subconjunto adecuado de los lenguajes sensibles al contexto . ^[1] Se los califica como una familia abstracta de lenguajes (además de ser un AFL completo) y, por lo tanto, satisfacen muchas propiedades de clausura. Sin embargo, no están cerrados bajo 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 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 ligeramente sensible al contexto, conocida actualmente como gramáticas indexadas lineales (LIG). ^[5] Las gramáticas indexadas lineales tienen restricciones adicionales en relación con las IG. Las LIG son débilmente equivalentes (generan la misma clase de lenguaje) que las gramáticas contiguas a árboles . ^[6]

Ejemplos

Los siguientes idiomas están indexados, pero no son libres de contexto:

${\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n\geq 1\}}$ ^[3]

${\displaystyle \{a^{n}b^{m}c^{n}d^{m}|m,n\geq 0\}}$ ^[2]

Estos dos idiomas también están indexados, pero ni siquiera son mínimamente sensibles al contexto según la caracterización de Gazdar:

${\displaystyle \{a^{2^{n}}|n\geq 0\}}$ ^[2]

${\displaystyle \{www|w\in \{a,b\}^{+}\}}$ ^[3]

Por otra parte, el siguiente idioma no está indexado: ^[7]

${\displaystyle \{(ab^{n})^{n}|n\geq 0\}}$

Propiedades

Hopcroft y Ullman tienden a considerar a los lenguajes indexados como una clase "natural", ya que son generados por varios formalismos, tales como: ^[9]

• Gramáticas indexadas de Aho ^[1]
• Autómatas de pila anidada unidireccional de Aho ^[10]
• Las macrogramá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 las gramáticas indexadas. Por el contrario, Gilman ^[7] ofrece un "lema de contracción" para los lenguajes indexados.

Véase también

• Jerarquía de Chomsky

Referencias

1. 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.
2. Partee, Barbara ; ter Meulen, Alice ; Wall, Robert E. (1990). Métodos matemáticos en lingüística . Kluwer Academic Publishers. págs. 536–542. ISBN 978-90-277-2245-4.
3. Gazdar, Gerald (1988). "Aplicabilidad de las gramáticas indexadas a las lenguas naturales". En Reyle, U.; Rohrer, C. (eds.). Análisis sintáctico de lenguas naturales y teorías lingüísticas . Estudios en lingüística y filosofía. Vol. 35. Springer Netherlands. págs. 69–94. doi :10.1007/978-94-009-1337-0_3. ISBN 978-94-009-1337-0.
4. Vijayashanker, K. (1987). Un estudio de gramáticas de árboles adyacentes (Tesis). ProQuest  303610666.
5. Kallmeyer, Laura (2010). Análisis sintáctico más allá de las gramáticas independientes del contexto. Springer. pág. 31. ISBN 978-3-642-14846-0.
6. Kallmeyer, Laura (16 de agosto de 2010). Análisis más allá de las gramáticas independientes del contexto. Springer. p. 32. ISBN 978-3-642-14846-0.
7. Gilman, Robert H. (1996). "Un lema de contracción para lenguajes indexados". Ciencias de la computación teórica . 163 (1–2): 277–281. arXiv : math/9509205 . doi :10.1016/0304-3975(96)00244-7. S2CID  14479068.
8. Hopcroft, John ; Ullman, Jeffrey (1979). Introducción a la teoría de autómatas, lenguajes y computación. Addison-Wesley. p. 390. ISBN 978-0-201-02988-8.
9. Introducción a la teoría de autómatas, lenguajes y computación, ^[8] Notas bibliográficas, p.394-395
10. 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.
11. Fischer, Michael J. (octubre de 1968). "Gramáticas con producciones similares a las macro". Noveno Simposio Anual sobre Teoría de Conmutación y Autómatas (Swat 1968) . Noveno Simposio Anual sobre Teoría de Conmutación y Autómatas (swat 1968). págs. 131–142. doi :10.1109/SWAT.1968.12.
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.
13. Maibaum, TSE (junio de 1974). "Un enfoque generalizado de los lenguajes formales". Revista de Ciencias de la Computación y de Sistemas . 8 (3): 409–439. doi : 10.1016/s0022-0000(74)80031-0 .
14. Hayashi, Takeshi (1973). "Sobre árboles de derivación de gramáticas indexadas: una extensión del teorema {$uvwxy$}". Publicaciones del Instituto de Investigación en Ciencias Matemáticas . 9 (1): 61–92. doi : 10.2977/prims/1195192738 .

Enlaces externos

• Capítulo "PNL en Prolog" sobre gramáticas y lenguajes indexados