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:
“Repeat thy song, till the familiar lines
Are footpaths for the thought of Italy!
Thy flame is blown abroad from all the heights,
Through all the nations, and a sound is heard,
As of a mighty wind, and men devout,
Strangers of Rome, and the new proselytes,
In their own language hear thy wondrous word,
And many are amazed and many doubt.”
—Henry Wadsworth Longfellow (1809–1882)