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 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 languages. 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.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Indexed language — Indexed languages are a class of formal languages discovered by Alfred Aho [ cite journal | last = Aho | first = Alfred | year = 1968 | title = Indexed grammars an extension of context free grammars | journal = Journal of the ACM | volume = 15 |… …   Wikipedia

  • Controlled grammar — Controlled grammars[1] are a class of grammars that extend, usually, the context free grammars with additional controls on the derivations of a sentence in the language. A number of different kinds of controlled grammars exist, the four main… …   Wikipedia

  • Context-free grammar — In formal language theory, a context free grammar (CFG) is a formal grammar in which every production rule is of the form V → w where V is a single nonterminal symbol, and w is a string of terminals and/or nonterminals (w can be empty). The… …   Wikipedia

  • Context-sensitive grammar — A context sensitive grammar (CSG) is a formal grammar in which the left hand sides and right hand sides of any production rules may be surrounded by a context of terminal and nonterminal symbols. Context sensitive grammars are more general than… …   Wikipedia

  • Discontinuous-constituent phrase structure grammar — (DCPSG) (distinct from Discontinuous Phrase Structure Grammar/DPSG) is a formalism for describing discontinuous phrase structures in natural language, such as verb phrases in VSO languages. The formalism was introduced in the slightly more… …   Wikipedia

  • Minimalist grammar — Minimalist grammars are a class of formal grammars that aim to provide a more rigorous, usually proof theoretic, formalization of Chomskyan Minimalist program than is normally provided in the mainstream Minimalist literature. A variety of… …   Wikipedia

  • Pipil grammar — This article provides a grammar sketch of the Nawat or Pipil language, an endangered language spoken by the Pipils of western El Salvador, belonging to the Nahua group within the Uto Aztecan language family. There also exists a brief typological… …   Wikipedia

  • Deterministic context-free grammar — In formal grammar theory, the deterministic context free grammars (DCFGs) are a proper subset of the context free grammars. The deterministic context free grammars are those a deterministic pushdown automaton can recognize. A DCFG is the finite… …   Wikipedia

  • Head-driven phrase structure grammar — (HPSG) is a highly lexicalized, non derivational generative grammar theory developed by Carl Pollard and Ivan Sag (1985). It is the immediate successor to generalized phrase structure grammar. HPSG draws from other fields such as computer science …   Wikipedia

  • Miskito grammar — This article provides a grammar sketch of the Miskito language, the language of the Miskito people of the Atlantic coast of Nicaragua and Honduras, a member of the Misumalpan language family. There also exists a brief typological overview of the… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”