Indexed language explained

Indexed languages are a class of formal languages discovered by Alfred Aho;^[1] they are described by indexed grammars and can be recognized by nested stack automata.^[2]

Indexed languages are a proper subset of context-sensitive languages.^[1] They qualify as an abstract family of languages (furthermore a full AFL) and hence satisfy many closure properties. However, they are not closed under intersection or complement.

The class of indexed languages has generalization of context-free languages, since indexed grammars can describe many of the nonlocal constraints occurring in natural languages.

Gerald Gazdar (1988)^[3] and Vijay-Shanker (1987)^[4] introduced a mildly context-sensitive language class now known as linear indexed grammars (LIG).^[5] Linear indexed grammars have additional restrictions relative to IG. LIGs are weakly equivalent (generate the same language class) as tree adjoining grammars.^[6]

Examples

The following languages are indexed, but are not context-free:

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

These two languages are also indexed, but are not even mildly context sensitive under Gazdar's characterization:

\{a ^{2 ^{n}} | n \geq 0 \} ^[2] \{www | w \in \{a,b\} ^{+} \} ^[3]

On the other hand, the following language is not indexed:^[7]

\{(a b ^{n)} ^{n} | n \geq 0 \}

Properties

Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:

• Aho's indexed grammars^[1]
• Aho's one-way nested stack automata^[8]
• Fischer's macro grammars^[9]
• Greibach's automata with stacks of stacks^[10]
• Maibaum's algebraic characterization^[11]

Hayashi^[12] generalized the pumping lemma to indexed grammars.Conversely, Gilman^[7] gives a "shrinking lemma" for indexed languages.

See also

• Chomsky hierarchy

External links

• "NLP in Prolog" chapter on indexed grammars and languages

Notes and References

1. Aho . Alfred Aho . Alfred . 9539666 . 1968 . Indexed grammars—an extension of context-free grammars . . 15 . 4 . 647–671 . 10.1145/321479.321488 . free .
2. Book: Barbara Partee . Partee . Barbara . Alice . ter Meulen. Alice ter Meulen . Robert E. . Wall . Mathematical Methods in Linguistics . 1990 . Kluwer Academic Publishers . 536–542 . 978-90-277-2245-4 .
3. Book: Gazdar . Gerald . Applicability of Indexed Grammars to Natural Languages . 69–94 . 10.1007/978-94-009-1337-0_3 . U. . Reyle . C. . Rohrer . Natural Language Parsing and Linguistic Theories . Studies in Linguistics and Philosophy . 1988 . 35 . Springer Netherlands . 978-94-009-1337-0 .
4. Vijayashanker . K. . 1987 . A study of tree adjoining grammars . .
5. Book: Laura . Kallmeyer . Parsing Beyond Context-Free Grammars . 2010 . Springer . 978-3-642-14846-0 . 31 .
6. Book: Laura . Kallmeyer . Parsing Beyond Context-Free Grammars . 16 August 2010 . Springer . 978-3-642-14846-0 . 32 .
7. Gilman . Robert H. . 14479068 . A Shrinking Lemma for Indexed Languages. Theoretical Computer Science. 1996. 163. 1–2 . 277–281. 10.1016/0304-3975(96)00244-7. math/9509205.
8. Aho . Alfred V. . 685569 . Nested Stack Automata . Journal of the ACM . July 1969 . 16 . 3 . 383–406 . 10.1145/321526.321529 . free .
9. Fischer . Michael J. . 9th Annual Symposium on Switching and Automata Theory (Swat 1968) . Grammars with macro-like productions . 9th Annual Symposium on Switching and Automata Theory (swat 1968) . October 1968 . 131–142 . 10.1109/SWAT.1968.12 .
10. Greibach . Sheila A. . Full AFLs and nested iterated substitution . Information and Control . March 1970 . 16 . 1 . 7–35 . 10.1016/s0019-9958(70)80039-0 .
11. Maibaum . T.S.E. . A generalized approach to formal languages . Journal of Computer and System Sciences . June 1974 . 8 . 3 . 409–439 . 10.1016/s0022-0000(74)80031-0 . free .
12. Hayashi . Takeshi . On derivation trees of indexed grammars: an extension of the -theorem . Publications of the Research Institute for Mathematical Sciences . 1973 . 9 . 1 . 61–92 . 10.2977/prims/1195192738 . free .