Content deleted Content added
Tom.Reding (talk | contribs) m Enum 1 author/editor WL; WP:GenFixes on |
→Properties: clarified the Gilman-Shapiro result & connected it to the Muller-Schupp theorem |
||
| (12 intermediate revisions by 8 users not shown) | |||
Line 1:
{{Bots|deny=AWB}}<!--REASON: incorrectly identifies the first "{" in "{[[empty string{{!}}ε]]}" as an unbalanced bracket & removes it-->
[[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 [[
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>
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 58 ⟶ 60:
An example run (input string not shown):
{| class=wikitable
|-
! Action
Line 110 ⟶ 112:
==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
==Notes==
| |||