Indexed language

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.^[1]

The class of indexed languages has practical importance in natural language processing as a computationally affordable 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:^[8]

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

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

See also

• Chomsky hierarchy
• Indexed grammar
• Mildly context-sensitive language

References

1. Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671. doi:10.1145/321479.321488.
2. Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4.
3. Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages". In U. Reyle and C. Rohrer. Natural Language Parsing and Linguistic Theories. pp. 69–94.
4. http://search.proquest.com/docview/303610666
5. Laura Kallmeyer (2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 31. ISBN 978-3-642-14846-0.
6. Laura Kallmeyer (16 August 2010). Parsing Beyond Context-Free Grammars. Springer Science & Business Media. p. 32. ISBN 978-3-642-14846-0.
7. Gilman, Robert H. (1996). "A Shrinking Lemma for Indexed Languages" (PDF). Theoretical Computer Science 163 (1–2): 277–281. doi:10.1016/0304-3975(96)00244-7.
8. Introduction to automata theory, languages, and computation,^[9]Bibliographic notes, p.394-395
9. Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 0-201-02988-X.
10. Alfred Aho (1969). "Nested Stack Automata". Journal of the ACM 16 (3): 383–406. doi:10.1145/321526.321529.
11. Michael J. Fischer (1968). "Grammars with Macro-Like Productions". Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131–142.
12. Sheila A. Greibach (1970). "Full AFL's and Nested Iterated Substitution" (PDF). Information and Control 16 (1): 7–35. doi:10.1016/s0019-9958(70)80039-0.
13. T.S.E. Maibaum (1974). "A Generalized Approach to Formal Languages" (PDF). J. Computer and System Sciences 8 (3): 409–439. doi:10.1016/s0022-0000(74)80031-0.
14. T. Hayashi (1973). "On Derivation Trees of Indexed Grammars - An Extension of the uvxyz Theorem". Publication of the Research Institute for Mathematical Sciences (Research Institute for Mathematical Sciences) 9 (1): 61–92. doi:10.2977/prims/1195192738.
15. Robert H. Gilman (Sep 1995). "A Shrinking Lemma for Indexed Languages".

External links

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