Nested stack automaton

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. 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. 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. 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, and in fact the class of indexed languages is exactly the class of languages accepted by one-way nondeterministic nested stack automata. 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,Σ,Γ,δ,q0,Z0,F,,]⟩ where A configuration, or instantaneous description of such an automaton consists in a triple ⟨q,, ⟩,where