Indexed grammar

From Wikipedia, the free encyclopedia

An indexed grammar is a formal grammar which describes indexed languages. 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 \}$ ^[1]

with these rules (f and g are indices):

$S\to aAfc$

$A\to aAgc ~|~ B$

$Bf\to b$

$Bg\to 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. ^[1]

1 Linear indexed grammars
2 See also
3 References
4 External links

[edit] 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 languages. Membership in a linear indexed grammar can be decided in polynomial time. ^[2]

[edit] See also

[edit] References

^ ^a ^b Hopcroft, John; Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley, 390. ISBN 020102988X.
^ Gazdar, Gerald (1988). "Applicability of Indexed Grammars to Natural Languages", in U. Reyle and C. Rohrer: Natural Language Parsing and Linguistic Theories, 69-94.

[edit] External links

"NLP in Prolog" chapter on indexed grammars and languages

Automata theory: formal languages and formal grammars
Chomsky hierarchy	Grammars	Languages	Minimal automaton
Type-0	Unrestricted	Recursively enumerable	Turing machine
n/a	(no common name)	Recursive	Decider
Type-1	Context-sensitive	Context-sensitive	Linear-bounded
n/a	Indexed	Indexed	Nested stack
n/a	Tree-adjoining etc.	(Mildly context-sensitive)	Embedded pushdown
Type-2	Context-free	Context-free	Nondeterministic pushdown
n/a	Deterministic context-free	Deterministic context-free	Deterministic pushdown
Type-3	Regular	Regular	Finite
n/a		Star-free	Counter-Free
Each category of languages or grammars is a proper subset of the category directly above it, and any automaton in each category has an equivalent automaton in the category directly above it.