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^{[citation needed]} 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:

${\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]

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

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

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

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

${\displaystyle \{(ab^{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:^[9]

• 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] gives a "shrinking lemma" for indexed languages.

See also

• Chomsky hierarchy