# Nested stack automaton
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Nested_stack_automaton
> Markdown URL: https://mediated.wiki/source/Nested_stack_automaton.md
> Source: https://en.wikipedia.org/wiki/Nested_stack_automaton
> Source revision: 1319228188
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
{{Bots|deny=AWB}}
[[File:Pushdown-overview.svg|thumb|right|A nested stack automaton has the same devices as a [pushdown automaton](/source/pushdown_automaton), but has less restrictions for using them.]]
In [automata theory](/source/automata_theory), a '''nested stack automaton''' is a [finite automaton](/source/finite_automaton) that can make use of a [stack](/source/Stack_(data_structure)) containing data that can be additional stacks.[{{cite journal |last1=Aho |first1=Alfred V. |s2cid=685569 |authorlink1=Alfred Aho |title=Nested Stack Automata |journal=[Journal of the ACM](/source/Journal_of_the_ACM) |date=July 1969 |volume=16 |issue=3 |pages=383–406 |doi=10.1145/321526.321529 |doi-access=free }}]
Like a [stack automaton](/source/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](/source/indexed_language),[{{cite book | last = Partee | author-link = Barbara Partee | first = Barbara |author2=Alice ter Meulen |author2-link=Alice ter Meulen|author3=Robert E. Wall | title = Mathematical Methods in Linguistics | url = https://archive.org/details/mathematicalmeth00part_211| url-access = limited| year = 1990 | publisher = Kluwer Academic Publishers | pages = [https://archive.org/details/mathematicalmeth00part_211/page/n556 536]–542 | isbn = 978-90-277-2245-4 }}] and in fact the class of indexed languages is exactly the class of languages accepted by one-way [nondeterministic](/source/nondeterministic_algorithm) nested stack automata.[{{cite book| author=John E. Hopcroft, Jeffrey D. Ullman| title=Introduction to Automata Theory, Languages, and Computation| year=1979| publisher=Addison-Wesley| isbn=0-201-02988-X| url-access=registration| url=https://archive.org/details/introductiontoau00hopc}} Here:p.390]
Nested stack automata should not be confused with [embedded pushdown automata](/source/embedded_pushdown_automata), which have less computational power.{{citation needed|reason=The claim is currently supported only by the order in which both notions appear in the 'Automata theory: formal languages and formal grammars' overview table below.|date=February 2014}}
==Formal definition==
===Automaton===
A (nondeterministic two-way) nested stack automaton is a tuple {{angbr|''Q'',Σ,Γ,δ,''q''0,''Z''0,''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'' × ([Γ[*](/source/Kleene_star) ∪ ''D''), such that δ maps[Juxataposition denotes [string (set) concatenation](/source/string_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 Γ'.]
{|
|-
| || ''Q'' × Σ' × [Γ || into subsets of ''Q'' × ''D'' × [Γ[*](/source/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'' × {-1} || (reading mode),
|-
| || ''Q'' × Σ' × (Γ' ∪ [Γ') || into subsets of ''Q'' × ''D'' × [Γ*] || (stack creation mode), and
|-
| || ''Q'' × Σ' × {[''']'''} || into subsets of ''Q'' × ''D'' × {[ε](/source/empty_string)}, || (stack destruction mode),
|}
: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''0 ∈ ''Q'' is the initial state,
* ''Z''0 ∈ Γ 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''1''a''2...''a''''i''...''a''''n''-1],
[''Z''1''X''2...''X''''j''...''X''''m''-1''']'''
}},
where
* ''q'' ∈ ''Q'' is the current state,
* [''a''1''a''2...''a''''i''...''a''''n''-1] is the input string; for convenience, ''a''0 = [ and ''a''''n'' = ] is defined[Aho 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''1''X''2...''X''''j''...''X''''m''-1''']''' is the stack, including substacks; for convenience, ''X''1 = [''Z''1 [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.
===Example===
An example run (input string not shown):
{| class=wikitable
|-
! Action
! Step
! colspan=11 | Stack
|-
|
| 1:
| style="font-family:monospace"|[''a'' || style="font-family:monospace"| ''b'' || style="font-family:monospace"| [''k'' || style="font-family:monospace"| ] || style="font-family:monospace"| [''p'' || style="font-family:monospace"| ] || style="font-family:monospace"| ''c'' || style="font-family:monospace"| ''']'''
| colspan=3 |
|-
| create substack
| 2:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| [''p'' || style="font-family:monospace"| [''r'' || style="font-family:monospace"| ''s'' || style="font-family:monospace"| ] || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}
|-
| pop
| 3:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|[''p''}} || style="font-family:monospace"| [''s'' || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}
|
|-
| pop
| 4:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|[''p''}} || style="font-family:monospace"| [] || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}
| colspan=2 |
|-
| destroy substack
| 5:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|[''p''}} || style="font-family:monospace"| ] || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}
| colspan=4 |
|-
| move down
| 6:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|[''p''}} || style="font-family:monospace"| ] || style="font-family:monospace"| ''c'' || style="font-family:monospace"| {{color|#808080|''']'''}}
| colspan=4 |
|-
| move up
| 7:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|[''p''}} || style="font-family:monospace"| ] || style="font-family:monospace"| ''c'' || style="font-family:monospace"| {{color|#808080|''']'''}}
| colspan=4 |
|-
| move up
| 8:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| [''p'' || style="font-family:monospace"| ] || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}
| colspan=4 |
|-
| push
| 9:
| style="font-family:monospace"|{{color|#808080|[''a''}} || style="font-family:monospace"| {{color|#808080|''b''}} || style="font-family:monospace"| {{color|#808080|[''k''}} || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| [''n'' || style="font-family:monospace"| ''o'' || style="font-family:monospace"| ''p'' || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}
| colspan=2 |
|}
==Properties==
When automata are allowed to re-read their input ("[two-way automata](/source/Two-way_automaton)"), 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](/source/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](/source/Word_problem_for_groups) in [virtually free](/source/Virtually) [groups](/source/Group_(mathematics)), similarly to the [Muller–Schupp theorem](/source/Muller%E2%80%93Schupp_theorem).[{{cite tech report |last1=Shapiro |first1=Robert|last2 = Gilman|first2 = 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 }}]
==Notes==
{{Reflist|group=note}}
==References==
{{Reflist}}
{{Formal languages and grammars}}
Category:Models of computation
Category:Automata (computation)
---
Adapted from the Wikipedia article [Nested stack automaton](https://en.wikipedia.org/wiki/Nested_stack_automaton) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Nested_stack_automaton?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.