Nested stack automaton

Formal definition

Automaton

• 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 right endmarker for these strings,
• * ] is used as the final endmarker of the string denoting the whole stack.
• 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 ×, such that δ maps
• q₀ ∈ Q is the initial state,
• Z₀ ∈ Γ is the initial stack symbol,
• F ⊆ Q is the set of final states.

  Configuration

• q ∈ Q is the current state,
• is the input string; for convenience, a₀ = is defined The current position in the input, viz. i with 0 ≤ i ≤ n, is marked by underlining the respective symbol.
• is the stack, including substacks; for convenience, X₁ = is defined. The current position in the stack, viz. j with 1 ≤ j ≤ m, is marked by underlining the respective symbol.

  Example

Properties