Indexed language

From Wikipedia, the free encyclopedia

You have new messages (last change).

An indexed language is a formal language discovered by Alfred Aho.[1] They are a proper subset of context-sensitive languages, and a proper superset of context-free languages. They may be of the form:

L = \{a^n b^n c^n | n \geq 1 \} [2]

An indexed language is minimally characterized by an indexed grammar, or by a nested stack automaton. An indexed grammar may have a stack attached to nonterminals which get copied to daughter nonterminals. A nested stack automaton may read its stack, in addition to pushing or popping it. Also, a stack may nest other stacks inside of it. [3]

[edit] See also

[edit] References

  1. ^ Aho, Alfred (1968). "Indexed grammars—an extension of context-free grammars". Journal of the ACM 15 (4): 647–671.
  2. ^ Hopcroft, John, Jeffrey Ullman (1979). Introduction to automata theory, languages, and computation. Addison-Wesley, 390.
  3. ^ Partee, Barbara, Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers, 536–542.

[edit] External links


 This mathematics-related article is a stub. You can help Wikipedia by expanding it.


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
Type-2 Context-free Context-free Pushdown
Type-3 Regular Regular Finite
Each category of languages or grammars is a proper subset of the category directly above it.
Retrieved from "http://en.wikipedia.org../../../i/n/d/Indexed_language.html"