Content deleted Content added
m there is no reason parameter, use an html comment instead |
|||
Line 4:
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}}
| |||