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.
Read more about Indexed Language: Examples
Famous quotes containing the word language:
“Upon my tongues continual slanders ride,
The which in every language I pronounce,
Stuffing the ears of men with false reports.”
—William Shakespeare (1564–1616)