Nested stack automaton

From Wikipedia, the free encyclopedia

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.^[1] 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.^[2]

[edit] See also

• Automata theory

[edit] References

1. ^ Aho, Alfred (1969). "Nested stack automata". Journal of the ACM 16 (3): 383–406. doi:10.1145/321526.321529. ISSN 0004-5411. http://portal.acm.org/ft_gateway.cfm?id=321529&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=21501966&CFTOKEN=95121590. 
2. ^ Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers. pp. 536–542. ISBN 978-90-277-2245-4. 

v • d • e 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 n/a Star-free Aperiodic finite 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.

This computer science article is a stub. You can help Wikipedia by expanding it.