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 automatons.

Indexed languages are a proper subset of context-sensitive languages. 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. Gerald Gazdar has characterized the mildly context-sensitive languages in terms of linear indexed grammars.

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 \}$

$\{a^n b^m c^n d^m | m,n \geq 0 \}$

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

$\{a^{2^{n}} | n \geq 0 \}$

$\{www | w \in \{a,b\}^+ \}$

On the other hand, the following language is not indexed:

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

See also

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

External links

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