Nested stack automaton

A nested stack automaton has the same devices as a pushdown automaton, but has less restrictions for using them.

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

Nested stack automata should not be confused with embedded pushdown automata, which have less computational power.^{[ citation needed ]}

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. ^{[note 1]}
• 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 δ maps ^{[note 2]}

	Q × Σ' × [Γ	into subsets of Q × D × [Γ *	(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 × {-1}	(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; ^[4] 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 ⟨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 defined ^{[note 3]} 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₁ ^{[note 4]} 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	b	[k	]	[p	]	c	]
create substack	2:	[a	b	[k	]	[p	[r	s	]	]	c	]
pop	3:	[a	b	[k	]	[p	[s	]	]	c	]
pop	4:	[a	b	[k	]	[p	[]	]	c	]
destroy substack	5:	[a	b	[k	]	[p	]	c	]
move down	6:	[a	b	[k	]	[p	]	c	]
move up	7:	[a	b	[k	]	[p	]	c	]
move up	8:	[a	b	[k	]	[p	]	c	]
push	9:	[a	b	[k	]	[n	o	p	]	c	]

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

Gilman and Shapiro used nested stack automata to solve the word problem in certain groups. ^[6]

Notes

1. Aho originally used "$", "¢", and "#" instead of "[", "]", and "]", respectively. See Aho (1969), p.385 top.
2. 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 Γ'.
3. Aho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively.
4. The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol.

References

1. Aho, Alfred V. (July 1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi: 10.1145/321526.321529 . S2CID   685569.
2. Partee, Barbara; Alice ter Meulen; Robert E. Wall (1990). Mathematical Methods in Linguistics . Kluwer Academic Publishers. pp.  536–542. ISBN   978-90-277-2245-4.
3. John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation . Addison-Wesley. ISBN   0-201-02988-X. Here:p.390
4. Aho (1969), p.385 top
5. Beeri, C. (June 1975). "Two-way nested stack automata are equivalent to two-way stack automata". Journal of Computer and System Sciences. 10 (3): 317–339. doi: 10.1016/s0022-0000(75)80004-3 .
6. Shapiro, Robert Gilman Michael (4 December 1998). On groups whose word problem is solved by a nested stack automaton (Technical report). arXiv: math/9812028 . CiteSeerX   10.1.1.236.2029 . S2CID   12716492.