This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0009791447 Reproduction Date:
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]} Like a stack automaton, a nested stack automaton may step up or down in the stack, and read the current symbol; in addition, it may at any place create a new stack, operate on that one, eventually destroy it, and continue operating on the old stack. This way, stacks can be nested recursively to an arbitrary depth; however, the automaton always operates on the innermost stack only.
A nested stack automaton is capable of recognizing an indexed language,^{[2]} and in fact the class of indexed languages is exactly the class of languages accepted by one-way nondeterministic nested stack automata.^{[1]}^{[3]}
Nested stack automata should not be confused with embedded pushdown automata, which have less computational power.
A (nondeterministic two-way) nested stack automaton is a tuple ‹Q,Σ,Γ,δ,q_{0},Z_{0},F,[,],]› where
A configuration, or instantaneous description of such an automaton consists in a triple ‹ q, [a_{1}a_{2}...a_{i}...a_{n-1}], [Z_{1}X_{2}...X_{j}...X_{m-1}] ›, where
An example run (input string not shown):
When automata are allowed to re-read their input ("two-way automata"), nested stacks do not result in additional language recognition capabilities, compared to plain stacks.^{[5]}
Gilman and Shapiro used nested stack automata to solve the word problem in certain groups.^{[6]}
Computer science, Mathematics, Artificial intelligence, Theory of computation, Numerical analysis
Computer science, Automata theory, Formal language, String (computer science), Nondeterministic finite automaton
Computer science, Turing machine, Automata theory, Deterministic context-free language, Context-free language
Indexed grammar, Natural language processing, Formal language, Alfred Aho, Mildly context-sensitive language
Computer science, Mathematical logic, String (computer science), Automata theory, Concatenation
Nested word, Ptime, Automata theory, Formal language, Formal grammar
Formal language, Pumping lemma for context-free languages, Nested word, Automata theory, Formal grammar