Formal definition
Automaton
A (nondeterministic two-way) nested stack automaton is a tuple where * ''Q'', Σ, and Γ is a nonempty finite set of states, input symbols, and stack symbols, respectively, * and ] are distinct special symbols not contained in Σ ∪ Γ, ** is used as left endmarker for both the input string and a (sub)stack string, ** is used as right endmarker for these strings, ** ] is used as the final endmarker of the string denoting the whole stack.Aho originally used "$", "¢", and "#" instead of " , ", and "]", respectively. See Aho (1969), p.385 top. * An extended input alphabet is defined by Σ' = Σ ∪ { , an extended stack alphabet by Γ' = Γ ∪ {]}, and the set of input move directions by ''D'' = {-1,0,+1}. * δ, the finite control, is a mapping from ''Q'' × Σ' × (Γ' ∪ ' ∪ {'', ''''}) into finite subsets of ''Q'' × ''D'' × ( Kleene_star">*_∪_''D''),_such_that_δ_mapsConfiguration
A configuration, or instantaneous description of such an automaton consists in a triple , where * ''q'' ∈ ''Q'' is the current state, * [''a''1''a''2...''a''''i''...''a''''n''-1] is the input string; for convenience, ''a''0 = [ and ''a''''n'' = ] is definedAho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively. The current position in the input, viz. ''i'' with 0 ≤ ''i'' ≤ ''n'', is marked by underlining the respective symbol. * 1''X''2...''X''''j''...''X''''m''-1">'Z''1''X''2...''X''''j''...''X''''m''-1'' is the stack, including substacks; for convenience, ''X''1 = _and_''X''''m''_=_.html" ;"title="'Z''1 The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol. and ''X''''m'' = ">'Z''1 The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol. and ''X''''m'' = '' is defined. The current position in the stack, viz. ''j'' with 1 ≤ ''j'' ≤ ''m'', is marked by underlining the respective symbol.Example
An example run (input string not shown): {, , - ! Action ! Step ! colspan=11 , Stack , - , , 1: , style="font-family:monospace", [''a'' , , style="font-family:monospace", ''b'' , , style="font-family:monospace", [''k'' , , style="font-family:monospace", ] , , style="font-family:monospace", , , style="font-family:monospace", ">'p'' , , style="font-family:monospace", , , style="font-family:monospace", ''c'' , , style="font-family:monospace", ] , colspan=3 , , - , create substack , 2: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , style="font-family:monospace", [''r'' , , style="font-family:monospace", ''s'' , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , - , pop , 3: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", [''s'' , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , - , pop , 4: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", [] , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , colspan=2 , , - , destroy substack , 5: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", ] , , style="font-family:monospace", , , style="font-family:monospace", , colspan=4 , , - , move down , 6: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", ] , , style="font-family:monospace", ''c'' , , style="font-family:monospace", , colspan=4 , , - , move up , 7: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", ] , , style="font-family:monospace", ''c'' , , style="font-family:monospace", , colspan=4 , , - , move up , 8: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", ">'p'' , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , colspan=4 , , - , push , 9: , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", [''n'' , , style="font-family:monospace", ''o'' , , style="font-family:monospace", ''p'' , , style="font-family:monospace", , , style="font-family:monospace", , , style="font-family:monospace", , colspan=2 ,Properties
When automata are allowed to re-read their input ("Two-way automaton, 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 for groups, word problem in certain Group (mathematics), groups.Notes
References
{{Formal languages and grammars Models of computation Automata (computation)