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]
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: [7]
Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as: [9]
Hayashi [14] generalized the pumping lemma to indexed grammars. Conversely, Gilman [7] gives a "shrinking lemma" for indexed languages.
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]
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: [7]
Hopcroft and Ullman tend to consider indexed languages as a "natural" class, since they are generated by several formalisms, such as: [9]
Hayashi [14] generalized the pumping lemma to indexed grammars. Conversely, Gilman [7] gives a "shrinking lemma" for indexed languages.