- Indexed grammar
An indexed grammar is a
formal grammar which describesindexed language s. They have three disjoint sets of symbols: the usual terminals and nonterminals and the indices, which appear only in intermediate derivation steps.Productions can replace a nonterminal with a string of terminals and nonterminals like in context-free grammars, but also a nonterminal with a nonterminal followed by an index and a nonterminal followed by an index with a nonterminal.Indices can appear only after a nonterminal or after another index, so every nonterminal can be considered the "owner" of the indices that follow it, which form a stack (indices are added or removed by productions right after the nonterminal).
In practice, stacks of indices can count and remember what rules were applied and in which order. For example, indexed grammars can describe this non context free language:
:L = {a^n b^n c^n | n geq 1 } cite book | last = Hopcroft | first = John | coauthors =
Jeffrey Ullman | title =Introduction to automata theory, languages, and computation | year = 1979 | publisher = Addison-Wesley | pages = 390 | isbn = 020102988X ]with these rules (f and g are indices):
S o aAfc
A o aAgc ~|~ B
Bf o b
Bg o bB
The stack of g's that grows in the middle counts how many times (n-1) A has been expanded to add one a and one c; every g becomes a terminal b at the end.
The problem of determining whether a string is recognized by an indexed grammar is
NP-complete .Linear indexed grammars
Gerald Gazdar has defined a second class, the linear indexed grammars, by requiring that at most one nonterminal in each production be specified as receiving the stack; in a normal indexed grammar, all nonterminals receive copies of the stack. He showed that this new class of grammars defines a strictly smaller class of languages, the
mildly context sensitive language s. Membership in a linear indexed grammar can be decided in polynomial time. cite book | chapter=Applicability of Indexed Grammars to Natural Languages | year=1988 | last=Gazdar | first=Gerald | title=Natural Language Parsing and Linguistic Theories | editor=U. Reyle and C. Rohrer | pages=69-94]ee also
*
Chomsky hierarchy
*Indexed language References
External links
* [http://www.cogs.susx.ac.uk/research/nlp/gazdar/nlp-in-prolog/ch04/chapter-04-sh-1.6.3.html#sh-1.6.3 "NLP in Prolog" chapter on indexed grammars and languages]
Wikimedia Foundation. 2010.