Nested stack automaton explained

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.^[3]

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,Σ,Γ,δ,q₀,Z₀,F,[,],]) 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.^[4]
• An extended input alphabet is defined by Σ' = Σ ∪, an extended stack alphabet by Γ' = Γ ∪, and the set of input move directions by D = .
• δ, the finite control, is a mapping from Q × Σ' × (Γ' ∪ [Γ' ∪ {'''], [''']}) into finite subsets of Q × D × ([Γ<sup>[[Kleene star|*]] ∪ D), such that δ maps^[5]

Notes and References

1. Aho . Alfred V. . 685569 . Alfred Aho . Nested Stack Automata . Journal of the ACM . July 1969 . 16 . 3 . 383–406 . 10.1145/321526.321529 . free .
2. Book: Partee, Barbara . Barbara Partee . Alice ter Meulen . Alice ter Meulen. Robert E. Wall . Mathematical Methods in Linguistics . limited. 1990 . Kluwer Academic Publishers . 536–542 . 978-90-277-2245-4 .
3. Book: John E. Hopcroft, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. 1979. Addison-Wesley. 0-201-02988-X. registration. Here:p.390
4. Aho originally used "$", "¢", and "#" instead of "[", "]", and "
5. Aho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively.
6. Beeri . C. . Two-way nested stack automata are equivalent to two-way stack automata . Journal of Computer and System Sciences . June 1975 . 10 . 3 . 317–339 . 10.1016/s0022-0000(75)80004-3 . free .
7. Shapiro . Robert Gilman Michael . On groups whose word problem is solved by a nested stack automaton . 4 December 1998 . math/9812028 . 12716492 . 10.1.1.236.2029 .
8. Juxataposition denotes string (set) concatenation, and has a higher binding priority than set union ∪. For example, [Γ' denotes the set of all length-2 strings starting with "[" and ending with a symbol from Γ'.</ref> {| |- | &nbsp; &nbsp; &nbsp; || ''Q'' × Σ' × [Γ || into subsets of ''Q'' × ''D'' × [Γ<sup>[[Kleene star|*]] || (pushdown mode),|-| || Q × Σ' × Γ' || into subsets of Q × D × D || (reading mode),|-| || Q × Σ' × [Γ' || into subsets of ''Q'' × ''D'' × {+1} || (reading mode), |- | || ''Q'' × Σ' × {''']} || into subsets of Q × D × || (reading mode),|-| || Q × Σ' × (Γ' ∪ [Γ') || into subsets of ''Q'' × ''D'' × [Γ^*] || (stack creation mode), and|-| || Q × Σ' × || into subsets of Q × D ×, || (stack destruction mode),|}

   Informally, the top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol;<ref>Aho (1969), p.385 top</ref> then δ reads :* the current state, :* the current input symbol, and :* the current stack symbol, : and outputs :* the next state, :* the direction in which to move on the input, and :* the direction in which to move on the stack, or the string of symbols to replace the topmost stack symbol. * ''q''₀ ∈ ''Q'' is the initial state, * ''Z''₀ ∈ Γ is the initial stack symbol, * ''F'' ⊆ ''Q'' is the set of final states. ===Configuration=== A '''configuration''', or '''instantaneous description''' of such an automaton consists in a triple {{angbr| ''q'', [''a''₁''a''₂...<u>''a''_''i''</u>...''a''_''n''-1], [''Z''₁''X''₂...<u>''X''_''j''</u>...''X''_''m''-1''']}},where

   • q ∈ Q is the current state,
   • [''a''₁''a''₂...<u>''a''_''i''</u>...''a''_''n''-1] is the input string; for convenience, a₀ = [and ''a''_''n'' = ] is defined^[5] The current position in the input, viz. i with 0 ≤ i ≤ n, is marked by underlining the respective symbol.
   • [''Z''₁''X''₂...<u>''X''_''j''</u>...''X''_''m''-1'''] is the stack, including substacks; for convenience, X₁ = [''Z''₁ <ref group=note>The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol.</ref> 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	Stack
   	1:	[''a'' || style="font-family:monospace"| ''b'' || style="font-family:monospace"| [''k'' || style="font-family:monospace"| ] || style="font-family:monospace"| [''p''</u> || style="font-family:monospace"| ] || style="font-family:monospace"| c || style="font-family:monospace"| ]
   create substack	2:					[''p'' || style="font-family:monospace"| <u>[''r''</u> || 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''</u> || style="font-family:monospace"| {{color|#808080|]}} || 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"| ]	c
   move up	7:						]	c
   move up	8:					[''p''</u> || style="font-family:monospace"| ]
   push	9:					[''n''</u> || style="font-family:monospace"| ''o'' || style="font-family:monospace"| ''p'' || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| || style="font-family:monospace"| | colspan=2 |  |} 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.^[6] Gilman and Shapiro used nested stack automata to solve the word problem in certain groups.^[7] References