Nested stack automaton

In <a href="/facts/Automata_theory/Q6BmPv63">automata theory</a>, a nested stack automaton is a <a href="/facts/Finite_automaton/GMusWd0a">finite automaton</a> that can make use of a <a href="/facts/Stack_(data_structure)/bj7l94v1">stack</a> containing data which can be additional stacks. 
Like a <a href="/facts/Stack_automaton/kEPRC70F">stack automaton</a>, 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 <a href="/facts/Indexed_language/XXFzlent">indexed language</a>, and in fact the class of indexed languages is exactly the class of languages accepted by one-way <a href="/facts/Nondeterministic_algorithm/UubLdp3D">nondeterministic</a> nested stack automata.
Nested stack automata should not be confused with <a href="/facts/Embedded_pushdown_automata/czqRpAvl">embedded pushdown automata</a>, which have less computational power.

Nested stack automaton open-in-new

Nested stack automaton