# 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] Gerald Gazdar has characterized the mildly context-sensitive languages in terms of linear indexed grammars.[3]

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.

## 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:[4]

$\{(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, viz.[6]

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

## References

1. ^ a b c d 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. ^ a b c 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. ^ a b c 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. ^ a b Gilman, Robert H. (1996). "A Shrinking Lemma for Indexed Languages". Theoretical Computer Science 163 (1–2): 277–281. doi:10.1016/0304-3975(96)00244-7. edit
5. ^ Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley. p. 390. ISBN 0-201-02988-X.
6. ^ Introduction to automata theory, languages, and computation,[5]Bibliographic notes, p.394-395
7. ^ Alfred Aho (1969). "Nested Stack Automata". Journal of the ACM 16 (3): 383–406.
8. ^ Michael J. Fischer (1968). "Grammars with Macro-Like Productions". Proc. 9th Ann. IEEE Symp. on Switching and Automata Theory (SWAT). pp. 131–142.
9. ^ Sheila A. Greibach (1970). "Full AFL's and Nested Iterated Substitution". Information and Control 16 (1): 7–35.
10. ^ T.S.E. Maibaum (1974). "A Generalized Approach to Formal Languages". J. Computer and System Sciences 8 (3): 409–439.
11. ^ 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.
12. ^ Robert H. Gilman (Sep 1995). A Shrinking Lemma for Indexed Languages.