Indexed language
Encyclopedia
Indexed languages are a class of formal language
s discovered by Alfred Aho
; they are described by indexed grammar
s and can be recognized by nested stack automaton
s.
Indexed languages are a proper subset
of context-sensitive language
s. 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 grammar
s can describe many of the nonlocal constraints occurring in natural languages.
:
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 :
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
s discovered by Alfred Aho
Alfred Aho
Alfred Vaino Aho is a Canadian computer scientist.-Career:Aho received a B.A.Sc. in Engineering Physics from the University of Toronto and a Ph.D. in Electrical Engineering/Computer Science from Princeton University...
; they are described by indexed grammar
Indexed grammar
An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals, as well as index symbols, which appear only in intermediate derivation steps on a stack associated with the non-terminals of that step.The...
s and can be recognized by nested stack automaton
Nested stack automaton
In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks. A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an indexed language....
s.
Indexed languages are a proper subset
Subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of context-sensitive language
Context-sensitive language
In theoretical computer science, a context-sensitive language is a formal language that can be defined by a context-sensitive grammar. That is one of the four types of grammars in the Chomsky hierarchy...
s. They qualify as an abstract family of languages
Abstract family of languages
In computer science, in particular in the field of formal language theory,the term abstract family of languages refers to an abstract mathematical notion generalizing characteristics common to the regular languages, the context-free languages and the recursively enumerable languages, and other...
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
Natural language processing
Natural language processing is a field of computer science and linguistics concerned with the interactions between computers and human languages; it began as a branch of artificial intelligence....
as a computationally affordable generalization of context-free languages, since indexed grammar
Indexed grammar
An indexed grammar is a formal grammar which describes indexed languages. They have three disjoint sets of symbols: the usual terminals and nonterminals, as well as index symbols, which appear only in intermediate derivation steps on a stack associated with the non-terminals of that step.The...
s can describe many of the nonlocal constraints occurring in natural languages.
Examples
The following languages are indexed, but are not context-freeContext-free language
In formal language theory, a context-free language is a language generated by some context-free grammar. The set of all context-free languages is identical to the set of languages accepted by pushdown automata.-Examples:...
:
These two languages are also indexed, but are not even mildly context sensitive
Mildly context-sensitive language
In formal grammar theory, mildly context-sensitive languages are a class of formal languages which can be efficiently parsed, but still possess enough context sensitivity to allow the parsing of natural languages. The concept was first introduced by Aravind Joshi in 1985.-Definition:Mild...
under Gazdar's characterization:
On the other hand, the following language is not indexed :