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 and a proper superset of mildly context-sensitive languages and context-free languages. They qualify as an abstract family of languages and hence satisfy many closure properties. However, they are not closed under ...
more
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 and a proper superset of mildly context-sensitive languages and context-free languages. They qualify as an abstract family of languages 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.
The following languages are indexed, but are not context-free:
These two languages are also indexed, but are not even mildly context sensitive under...
less
