Nested stack automaton: Difference between revisions

Revision as of 01:20, 18 August 2020

Revision as of 15:46, 19 December 2020

Line 1:

[[File:Pushdown-overview.svg|thumb|right|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 state machine|finite automaton]] that can make use of a [[Stack (data structure)|stack]] containing data which can be additional stacks.<ref name="aho">{{cite journal |last1=Aho |first1=Alfred V. |s2cid=685569 |authorlink1=Alfred Aho |title=Nested Stack Automata |journal=Journal of the ACM |date=July 1969 |volume=16 |issue=3 |pages=383–406 |doi=10.1145/321526.321529 }} </ref>

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]],<ref> {{cite book | last = [[Partee | author-link = Barbara Partee|Partee]] | first = Barbara |author2=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 }} </ref> and in fact the class of indexed languages is exactly the class of languages accepted by one-way [[nondeterministic algorithm|nondeterministic]] nested stack automata.<ref name="aho" /><ref>{{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</ref>

Nested stack automata should not be confused with [[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}}

Line 42:

* ''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

Line 53 ⟶ 54:

* [''a''₁''a''₂...<u>''a''_''i''</u>...''a''_''n''-1] is the input string; for convenience, ''a''₀ = [ and ''a''_''n'' = ] is defined<ref group=note>Aho originally used the left and right stack marker, viz. $ and ¢, as right and left input marker, respectively.</ref> The current position in the input, viz. ''i'' with 0 ≤ ''i'' ≤ ''n'', is marked by underlining the respective symbol.

* [''Z''₁''X''₂...<u>''X''_''j''</u>...''X''_''m''-1''']''' is the stack, including substacks; for convenience, ''X''₁ = [''Z''₁ <ref group=note>The top symbol of a (sub)stack together with its preceding left endmarker "[" is viewed as a single symbol.</ref> 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):

Line 113 ⟶ 115:

==Notes==

{{reflistReflist|group=note}}

==References==

{{Reflist}}

<references/>

{{Formal languages and grammars}}

[[Category:Models of computation]]

[[Category:Automata (computation)]]