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. 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.[1]
[edit] See also
[edit] References
- ^ Partee, Barbara; Alice ter Meulen, and Robert E. Wall (1990). Mathematical Methods in Linguistics. Kluwer Academic Publishers, 536–542. ISBN 978-90-277-2245-4.
| 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 |
| Type-2 | Context-free | Context-free | Nondeterministic Pushdown |
| n/a | Deterministic Context-free | Deterministic Context-free | Deterministic Pushdown |
| Type-3 | Regular | Regular | Finite |
| Each category of languages or grammars is a proper subset of the category directly above it. | |||
