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.

Formal definition

Automaton

A (nondeterministic two-way) nested stack automaton is a tuple ⟨Q,Σ,Γ,δ,q0,Z0,F,[,],]⟩ where

Configuration

A configuration, or instantaneous description of such an automaton consists in a triple ⟨q, [a1a2... ai ...an-1], [Z1X2... Xj ...Xm-1]⟩, where

Example

An example run (input string not shown):

Properties

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. Gilman and Shapiro used nested stack automata to solve the word problem in certain groups.