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 automatons.[2]

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