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:
“Just as language has no longer anything in common with the thing it names, so the movements of most of the people who live in cities have lost their connexion with the earth; they hang, as it were, in the air, hover in all directions, and find no place where they can settle.”
—Rainer Maria Rilke (1875–1926)