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.^[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.^{[citation needed]}