Nested stack automaton

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] 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, [a1a2...ai...an-1], [Z1X2...Xj...Xm-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.