Nested stack automaton: Difference between revisions

Revision as of 15:25, 16 April 2012

Latest revision as of 16:57, 24 March 2025

(44 intermediate revisions by 23 users not shown)

Line 1:

{{Bots|deny=AWB}}<!--REASON: incorrectly identifies the first "{" in "{[[empty string{{!}}ε]]}" as an unbalanced bracket & removes it-->

{{merge-to|Embedded pushdown automaton|discuss=Talk:Nested stack automaton#Merge proposal|date=April 2012}}

[[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 last |first1= [[Alfred Aho|Aho]]V. | first s2cid= Alfred685569 | year authorlink1=Alfred 1969Aho | title = Nested stackStack automataAutomata | journal = [[Journal of the ACM]] |date=July 1969 |volume = 16 | issue = 3 | pages = 383–406 | issn = 0004-5411 | url = http://portal.acm.org/ft_gateway.cfm?id=321529&type=pdf&coll=GUIDE&dl=GUIDE,&CFID=21501966&CFTOKEN=95121590 | doi = 10.1145/321526.321529 }} </ref> A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack automaton is capable of recognizing an [[indexed language]]<ref> {{cite book | last doi-access= [[Barbara Partee|Partee]] | first = Barbara | coauthors = Alice ter Meulen, and Robert E. Wall | title = Mathematical Methods in Linguistics | year = 1990 | publisher = Kluwer Academic Publishers | pages = 536–542 | isbn = 978-90-277-2245-4free }} </ref>, and in fact the class of indexed languages is exactly the class of languages accepted by one-way [[nondeterministic]] nested stack automata.<ref name="aho" />

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 | 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 }}</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>

==See also==

* [[Automata theory]]

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}}

==Formal definition==

===Automaton===

A (nondeterministic two-way) nested stack automaton is a tuple {{angbr|''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.<ref group=note>Aho originally used "$", "¢", and "#" instead of "[", "]", and "''']'''", respectively. See Aho (1969), p.385 top.</ref>

* 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'' × ([Γ^{[[Kleene star|*]]} ∪ ''D''), such that δ maps<ref group=note>Juxataposition denotes [[string concatenation#Concatenation of sets of strings|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 Γ'.</ref>

{|

|-

| &nbsp; &nbsp; &nbsp; || ''Q'' × Σ' × [Γ || into subsets of ''Q'' × ''D'' × [Γ^{[[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'' × {[[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;<ref>Aho (1969), p.385 top</ref> 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

{{angbr|

''q'',

[''a''₁''a''₂...<u>''a''_''i''</u>...''a''_''n''-1],

[''Z''₁''X''₂...<u>''X''_''j''</u>...''X''_''m''-1''']'''

}},

where

* ''q'' ∈ ''Q'' is the current state,

* [''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):

{| class=wikitable

|-

! Action

! Step

! colspan=11 | Stack

|-

|

| 1: &nbsp; &nbsp; &nbsp;

| style="font-family:monospace"|[''a'' || style="font-family:monospace"| ''b'' || style="font-family:monospace"| [''k'' || style="font-family:monospace"| ] || style="font-family:monospace"| <u>[''p''</u> || style="font-family:monospace"| ] || style="font-family:monospace"| ''c'' || style="font-family:monospace"| ''']'''

| colspan=3 | &nbsp;

|-

| create substack &nbsp; &nbsp; &nbsp;

| 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"| <u>[''r''</u> || 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"| <u>[''s''</u> || 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|''']'''}}

| &nbsp;

|-

| 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"| <u>[]</u> || style="font-family:monospace"| {{color|#808080|]}} || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}

| colspan=2 | &nbsp;

|-

| 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"| <u>]</u> || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}

| colspan=4 | &nbsp;

|-

| 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"| <u>''c''</u> || style="font-family:monospace"| {{color|#808080|''']'''}}

| colspan=4 | &nbsp;

|-

| 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"| <u>]</u> || style="font-family:monospace"| ''c'' || style="font-family:monospace"| {{color|#808080|''']'''}}

| colspan=4 | &nbsp;

|-

| 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"| <u>[''p''</u> || style="font-family:monospace"| ] || style="font-family:monospace"| {{color|#808080|''c''}} || style="font-family:monospace"| {{color|#808080|''']'''}}

| colspan=4 | &nbsp;

|-

| 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"| <u>[''n''</u> || 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 | &nbsp;

|}

==Properties==

When automata are allowed to re-read their input ("[[Two-way automaton|two-way automata]]"), nested stacks do not result in additional language recognition capabilities, compared to plain stacks.<ref>{{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 |date=June 1975 |volume=10 |issue=3 |pages=317–339 |doi=10.1016/s0022-0000(75)80004-3 |doi-access=free }}</ref>

Gilman and Shapiro used nested stack automata to solve the [[Word problem for groups|word problem]] in [[Virtually#Virtually_free|virtually free]] [[Group (mathematics)|groups]], similarly to the [[Muller–Schupp theorem]].<ref>{{cite tech report |last1=Shapiro |first1=Robert Gilman 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 }}</ref>

==Notes==

{{Reflist|group=note}}

==References==

{{Reflist}}

<references/>

{{Formal languages and grammars}}

{{comp-sci-stub}}

[[Category:Models of computation]]

[[Category:Automata theory]]

[[Category:Models of computation]]

[[hr:Automat s ugniježđenim stogom]]

[[Category:Automata (computation)]]

[[sr:Аутомат са угњежденим стеком]]

[[zh:嵌套堆栈自动机]]