Indexed language


Indexed languages are a class of formal languages discovered by Alfred Aho; they are described by indexed grammars and can be recognized by nested stack automata.
Indexed languages are a proper subset of context-sensitive languages. They qualify as an abstract family of languages 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 and Vijay-Shanker introduced a mildly context-sensitive language class now known as linear indexed grammars. Linear indexed grammars have additional restrictions relative to IG. LIGs are weakly equivalent as tree adjoining grammars.

Examples

The following languages are indexed, but are not context-free:
These two languages are also indexed, but are not even mildly context sensitive under Gazdar's characterization:
On the other hand, the following language is not indexed:

Properties

and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as:
Hayashi generalized the pumping lemma to indexed grammars.
Conversely, Gilman gives a "shrinking lemma" for indexed languages.