Nested stack automaton: Difference between revisions

Content deleted Content added
No edit summary
AnomieBOT (talk | contribs)
m Dating maintenance tags: {{Merge-to}}
Line 1:
{{merge-to|Embedded pushdown automaton|discuss=Talk:Nested stack automaton#Merge proposal|date=April 2012}}
 
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 | last = [[Alfred Aho|Aho]] | first = Alfred | year = 1969 | title = Nested stack automata | journal = [[Journal of the ACM]] | 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 = [[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-4 }} </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" />