Nested stack automaton

Last updated December 23, 2024

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.

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

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

Related Research Articles

In the theory of computation, a branch of theoretical computer science, a pushdown automaton (PDA) is a type of automaton that employs a stack.

Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science with close connections to mathematical logic. The word automata comes from the Greek word αὐτόματος, which means "self-acting, self-willed, self-moving". An automaton is an abstract self-propelled computing device which follows a predetermined sequence of operations automatically. An automaton with a finite number of states is called a finite automaton (FA) or finite-state machine (FSM). The figure on the right illustrates a finite-state machine, which is a well-known type of automaton. This automaton consists of states and transitions. As the automaton sees a symbol of input, it makes a transition to another state, according to its transition function, which takes the previous state and current input symbol as its arguments.

In computer science and automata theory, a deterministic Büchi automaton is a theoretical machine which either accepts or rejects infinite inputs. Such a machine has a set of states and a transition function, which determines which state the machine should move to from its current state when it reads the next input character. Some states are accepting states and one state is the start state. The machine accepts an input if and only if it will pass through an accepting state infinitely many times as it reads the input.

In the theory of computation, a branch of theoretical computer science, a deterministic finite automaton (DFA)—also known as deterministic finite acceptor (DFA), deterministic finite-state machine (DFSM), or deterministic finite-state automaton (DFSA)—is a finite-state machine that accepts or rejects a given string of symbols, by running through a state sequence uniquely determined by the string. Deterministic refers to the uniqueness of the computation run. In search of the simplest models to capture finite-state machines, Warren McCulloch and Walter Pitts were among the first researchers to introduce a concept similar to finite automata in 1943.

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if

In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into existential and universal transitions. For example, let A be an alternating automaton.

A finite-state transducer (FST) is a finite-state machine with two memory tapes, following the terminology for Turing machines: an input tape and an output tape. This contrasts with an ordinary finite-state automaton, which has a single tape. An FST is a type of finite-state automaton (FSA) that maps between two sets of symbols. An FST is more general than an FSA. An FSA defines a formal language by defining a set of accepted strings, while an FST defines a relation between sets of strings.

The ω-regular languages are a class of ω-languages that generalize the definition of regular languages to infinite words.

In automata theory, a deterministic pushdown automaton is a variation of the pushdown automaton. The class of deterministic pushdown automata accepts the deterministic context-free languages, a proper subset of context-free languages.

In computer science, in particular in automata theory, a two-way finite automaton is a finite automaton that is allowed to re-read its input.

In quantum computing, quantum finite automata (QFA) or quantum state machines are a quantum analog of probabilistic automata or a Markov decision process. They provide a mathematical abstraction of real-world quantum computers. Several types of automata may be defined, including measure-once and measure-many automata. Quantum finite automata can also be understood as the quantization of subshifts of finite type, or as a quantization of Markov chains. QFAs are, in turn, special cases of geometric finite automata or topological finite automata.

A queue machine, queue automaton, or pullup automaton (PUA) is a finite-state machine with the ability to store and retrieve data from an infinite-memory queue. Its design is similar to a pushdown automaton but differs by replacing the stack with this queue. A queue machine is a model of computation equivalent to a Turing machine, and therefore it can process the same class of formal languages.

A read-only Turing machine or two-way deterministic finite-state automaton (2DFA) is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a deterministic finite automaton in computational power, and therefore can only parse a regular language.

An embedded pushdown automaton or EPDA is a computational model for parsing languages generated by tree-adjoining grammars (TAGs). It is similar to the context-free grammar-parsing pushdown automaton, but instead of using a plain stack to store symbols, it has a stack of iterated stacks that store symbols, giving TAGs a generative capacity between context-free and context-sensitive grammars, or a subset of mildly context-sensitive grammars. Embedded pushdown automata should not be confused with nested stack automata which have more computational power.

In computer science, more specifically in automata and formal language theory, nested words are a concept proposed by Alur and Madhusudan as a joint generalization of words, as traditionally used for modelling linearly ordered structures, and of ordered unranked trees, as traditionally used for modelling hierarchical structures. Finite-state acceptors for nested words, so-called nested word automata, then give a more expressive generalization of finite automata on words. The linear encodings of languages accepted by finite nested word automata gives the class of visibly pushdown languages. The latter language class lies properly between the regular languages and the deterministic context-free languages. Since their introduction in 2004, these concepts have triggered much research in that area.

In automata theory, a branch of theoretical computer science, an ω-automaton is a variation of a finite automaton that runs on infinite, rather than finite, strings as input. Since ω-automata do not stop, they have a variety of acceptance conditions rather than simply a set of accepting states.

In theoretical computer science, in particular in formal language theory, Kleene's algorithm transforms a given nondeterministic finite automaton (NFA) into a regular expression. Together with other conversion algorithms, it establishes the equivalence of several description formats for regular languages. Alternative presentations of the same method include the "elimination method" attributed to Brzozowski and McCluskey, the algorithm of McNaughton and Yamada, and the use of Arden's lemma.

In computer science, in particular in formal language theory, a quotient automaton can be obtained from a given nondeterministic finite automaton by joining some of its states. The quotient recognizes a superset of the given automaton; in some cases, handled by the Myhill–Nerode theorem, both languages are equal.

A tree stack automaton is a formalism considered in automata theory. It is a finite-state automaton with the additional ability to manipulate a tree-shaped stack. It is an automaton with storage whose storage roughly resembles the configurations of a thread automaton. A restricted class of tree stack automata recognises exactly the languages generated by multiple context-free grammars.

In automata theory, a self-verifying finite automaton (SVFA) is a special kind of a nondeterministic finite automaton (NFA) with a symmetric kind of nondeterminism introduced by Hromkovič and Schnitger. Generally, in self-verifying nondeterminism, each computation path is concluded with any of the three possible answers: yes, no, and I do not know. For each input string, no two paths may give contradictory answers, namely both answers yes and no on the same input are not possible. At least one path must give answer yes or no, and if it is yes then the string is considered accepted. SVFA accept the same class of languages as deterministic finite automata (DFA) and NFA but have different state complexity.

References

1 2 Aho, Alfred V. (July 1969). "Nested Stack Automata". Journal of the ACM. 16 (3): 383–406. doi: 10.1145/321526.321529 . S2CID 685569.
↑ 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.
↑ John E. Hopcroft, Jeffrey D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation . Addison-Wesley. ISBN 0-201-02988-X. Here:p.390
↑ Aho (1969), p.385 top
↑ 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 .
↑ 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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[4] Aho originally used "$", "¢", and "#" instead of "[", "]", and "]", respectively. See Aho (1969), p.385 top.

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

[7] Aho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively.

[8] The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol.

[aho-1] 1 2 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

[6] Aho (1969), p.385 top

[9] 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 .

[10] 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.

[1]

[2]

[3]

[note 1]

[note 2]

[4]

[note 3]

[note 4]

[5]

[6]