Nested stack automaton

A (nondeterministic two-way) nested stack automaton is a tuple {{angbr|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.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 × ([Γ^* ∪ D), such that δ mapsJuxataposition 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 Γ'.

:Informally, the top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol;Aho (1969), p.385 top 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.

A configuration, or instantaneous description of such an automaton consists in a triple

{{angbr|

q,

[a₁a₂...a_i...a_n-1],

[Z₁X₂...X_j...X_m-1]

}},

where

• q ∈ Q is the current state,
• [a₁a₂...a_i...a_n-1] is the input string; for convenience, a₀ = [ 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.
• [Z₁X₂...X_j...X_m-1] is the stack, including substacks; for convenience, X₁ = [Z₁ 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.

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.{{cite journal |last1=Beeri |first1=C. |title=Two-way nested stack automata are equivalent to two-way stack automata |journal=Journal of Computer and System Sciences |date=June 1975 |volume=10 |issue=3 |pages=317–339 |doi=10.1016/s0022-0000(75)80004-3 |doi-access=free }}

Gilman and Shapiro used nested stack automata to solve the word problem in virtually free groups, similarly to the Muller–Schupp theorem.{{cite tech report |last1=Shapiro |first1=Robert Gilman Michael |title=On groups whose word problem is solved by a nested stack automaton |date=4 December 1998 |arxiv=math/9812028 |s2cid=12716492 |citeseerx=10.1.1.236.2029 }}

{{Reflist|group=note}}

{{Reflist}}

{{Formal languages and grammars}}

Category:Models of computation

Category:Automata (computation)