4966:
is equivalent to a TM with 3 tapes, where the first tape is the read-only input tape, and the 2nd and the 3rd tape are the 'push and pop' (stack) tapes. In order for such a PDA to simulate any given TM, we give the input of the PDA to the first tape, while keeping both the stacks empty. It then goes on to push all the input from the input tape to the first stack. When the entire input is transferred to the 1st stack, now we proceed like a normal TM, where moving right on the tape is the same as popping a symbol from the 1st stack and pushing a (possibly updated) symbol into the second stack, and moving left corresponds to popping a symbol from the 2nd stack and pushing a (possibly updated) symbol into the first stack. We hence have a PDA with 2 stacks that can simulate any TM.
6208:
5673:
6203:{\displaystyle {\begin{array}{lcl}\delta '(q_{1},w,x_{1})&\longrightarrow &(p_{1},\epsilon )\\\delta '(p_{1},\epsilon ,x_{2})&\longrightarrow &(p_{2},\epsilon )\\&\vdots &\\\delta '(p_{m-1},\epsilon ,x_{m})&\longrightarrow &(p_{m},\epsilon )\\\delta '(p_{m},\epsilon ,\epsilon )&\longrightarrow &(p_{m+1},y_{n})\\\delta '(p_{m+1},\epsilon ,\epsilon )&\longrightarrow &(p_{m+2},y_{n-1})\\&\vdots &\\\delta '(p_{m+n-1},\epsilon ,\epsilon )&\longrightarrow &(q_{2},y_{1}).\end{array}}}
136:
239:
36:
1540:
2775:
3700:
4965:
That a PDA is weaker than a TM can be brought down to the fact that the procedure 'pop' deletes some data. In order to make a PDA as strong as a TM, we need to save somewhere the data lost through 'pop'. We can achieve this by introducing a second stack. In the TM model of PDA of last paragraph, this
4961:
A pushdown automaton is computationally equivalent to a 'restricted' Turing
Machine (TM) with two tapes which is restricted in the following manner- On the first tape, the TM can only read the input and move from left to right (it cannot make changes). On the second tape, it can only 'push' and 'pop'
2514:
For each single pushdown automaton these two languages need to have no relation: they may be equal but usually this is not the case. A specification of the automaton should also include the intended mode of acceptance. Taken over all pushdown automata both acceptance conditions define the same family
4546:
can be transformed into an equivalent nondeterministic pushdown automaton. The derivation process of the grammar is simulated in a leftmost way. Where the grammar rewrites a nonterminal, the PDA takes the topmost nonterminal from its stack and replaces it by the right-hand part of a grammatical rule
5662:
266:
A pushdown automaton reads a given input string from left to right. In each step, it chooses a transition by indexing a table by input symbol, current state, and the symbol at the top of the stack. A pushdown automaton can also manipulate the stack, as part of performing a transition. The
1945:
there may be several possible steps. Any of these steps can be chosen in a computation. With the above definition in each step always a single symbol (top of the stack) is popped, replacing it with as many symbols as necessary. As a consequence no step is defined when the stack is empty.
4962:
data. Or equivalently, it can read, write and move left and right with the restriction that the only action it can perform at each step is to either delete the left-most character in the string (pop) or add an extra character left to the left-most character in the string (push).
4132:
4526:
5234:
292:. A given input string may drive a nondeterministic pushdown automaton to one of several configuration sequences; if one of them leads to an accepting configuration after reading the complete input string, the latter is said to belong to the
5454:
2409:
624:
2225:
5462:
250:
just looks at the input signal and the current state: it has no stack to work with, and therefore is unable to access previous values of the input. It can only choose a new state, the result of following the transition. A
6222:, which may additionally step left or right in the input string (surrounded by special endmarker symbols to prevent slipping out), and step up or down in the stack in read-only mode. A stack automaton is called
1615:
1128:
2928:
5062:
4323:
4228:
3937:
1836:
1446:
3929:
3834:
6359:
457:
6561:
Linear bounded automata are acceptors for the class of context-sensitive languages, which is a proper superclass of the context-free languages, and a proper subclass of Turing-recognizable (i.e.
4331:
891:
6313:
1523:
1048:
4609:
1758:
787:
5112:
2831:
2769:
1333:
6990:
2287:
267:
manipulation can be to push a particular symbol to the top of the stack, or to pop off the top of the stack. The automaton can alternatively ignore the stack, and leave it as it is.
4691:
1902:
1010:
3485:
3433:
3381:
3329:
1161:
270:
Put together: Given an input symbol, current state, and stack symbol, the automaton can follow a transition to another state, and optionally manipulate (push or pop) the stack.
3619:
1869:
3062:
3020:
2707:
2613:
2474:
1637:, which includes the current state, the part of the input tape that has not been read, and the contents of the stack (topmost symbol written first). The transition relation
1205:
2101:), which means after reading its input the automaton empties its stack. The first acceptance mode uses the internal memory (state), the second the external memory (stack).
2061:. There are two modes of accepting. The pushdown automaton either accepts by final state, which means after reading its input the automaton reaches an accepting state (in
6417:
6390:
4635:
3277:
3222:
2099:
1943:
917:
724:
693:
373:
3661:
2978:
2509:
2059:
1682:
329:
5165:
662:
5160:
4974:
A generalized pushdown automaton (GPDA) is a PDA that writes an entire string of some known length to the stack or removes an entire string from the stack in one step.
4836:
2438:
5320:
5306:
5273:
3732:
3689:
3166:
3143:
3099:
2658:
2564:
1655:
1074:
555:
530:
505:
353:
2294:
2251:
853:
1974:
560:
4940:
226:, by contrast, does allow access to and operations on deeper elements. Stack automata can recognize a strictly larger set of languages than pushdown automata. A
5134:
4911:
4891:
4871:
4791:
4771:
4711:
2633:
2539:
2110:
2079:
2014:
1994:
1702:
1635:
1265:
1245:
1225:
977:
957:
937:
827:
807:
480:
7310:
6983:
5657:{\displaystyle q_{1},q_{2}\in Q,w\in \Sigma _{\epsilon },x_{1},x_{2},\ldots ,x_{m}\in \Gamma ^{*},m\geq 0,y_{1},y_{2},\ldots ,y_{n}\in \Gamma ^{*},n\geq 0}
1050:
component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.
222:
can be regarded as being "pushed down" like a tray dispenser at a cafeteria, since the operations never work on elements other than the top element. A
4747:
The converse, finding a grammar for a given PDA, is not that easy. The trick is to code two states of the PDA into the nonterminals of the grammar.
7197:
6976:
4555:). In a sense the stack of the PDA contains the unprocessed data of the grammar, corresponding to a pre-order traversal of a derivation tree.
6894:
7122:
1550:
1083:
140:
2840:
7212:
6877:
Aizikowitz, Tamar; Kaminski, Michael (2011). "LR(0) Conjunctive
Grammars and Deterministic Synchronized Alternating Pushdown Automata".
4843:
4127:{\displaystyle (p,0011,Z)\vdash (p,011,AZ)\vdash (p,11,AAZ)\vdash (q,11,AAZ)\vdash (q,1,AZ)\vdash (q,\epsilon ,Z)\vdash (r,\epsilon ,Z)}
204:
139:
53:
7137:
4983:
4236:
4147:
6932:
6647:
1763:
1338:
141:
119:
3842:
3753:
7305:
7290:
4846:. Not all context-free languages are deterministic. As a consequence, the DPDA is a strictly weaker variant of the PDA. Even for
4558:
Technically, given a context-free grammar, the PDA has a single state, 1, and its transition relation is constructed as follows.
275:
100:
4551:). Where the grammar generates a terminal symbol, the PDA reads a symbol from input when it is the topmost symbol on the stack (
1547:
In order to formalize the semantics of the pushdown automaton a description of the current situation is introduced. Any 3-tuple
7352:
7166:
200:
72:
6318:
5311:
GPDA's and PDA's are equivalent in that if a language is recognized by a PDA, it is also recognized by a GPDA and vice versa.
7357:
4521:{\displaystyle (p,00111,Z)\vdash (p,0111,AZ)\vdash (p,111,AAZ)\vdash (q,111,AAZ)\vdash (q,11,AZ)\vdash (q,1,Z)\vdash (r,1,Z)}
387:
57:
79:
7183:
7108:
165:
143:
142:
6965:, another simulator for several machine types including nondeterministic pushdown automata (C++, Windows, Linux, MacOS)
858:
7280:
6237:
6272:
1451:
1015:
86:
7176:
6226:
if it never pops from the stack. The class of languages accepted by nondeterministic, nonerasing stack automata is
4851:
230:
allows full access, and also allows stacked values to be entire sub-stacks rather than just single finite symbols.
219:
4564:
1707:
736:
46:
7101:
5070:
332:
6842:
Ladner, Richard E.; Lipton, Richard J.; Stockmeyer, Larry J. (1984). "Alternating
Pushdown and Stack Automata".
2781:
2719:
7253:
7248:
4950:
1270:
68:
2256:
7334:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
6946:, in: G. Rozenberg, A. Salomaa (eds.), Handbook of Formal Languages, Vol. 1, Springer-Verlag, 1997, 111โ174.
5314:
One can formulate an analytic proof for the equivalence of GPDA's and PDA's using the following simulation:
4646:
1874:
982:
1949:
Computations of the pushdown automaton are sequences of steps. The computation starts in the initial state
7264:
7202:
7127:
6562:
4529:
The final state is accepting, but the input is not accepted this way as it has not been (completely) read.
227:
187:
Pushdown automata are used in theories about what can be computed by machines. They are more capable than
181:
6431:
of the resulting computations accepts. In a universal state APDA moves to all next states and accepts if
3440:
3388:
3336:
3284:
1133:
7207:
7155:
6968:
6534:
208:
161:
3574:
273:
If, in every situation, at most one such transition action is possible, then the automaton is called a
1841:
7300:
7275:
7132:
7093:
6538:
6500:
6490:
4725:
4543:
3029:
2987:
2447:
247:
188:
6663:
4942:
states. For many non-regular PDAs, any equivalent DPDA would require an unbounded number of states.
1907:
In general pushdown automata are nondeterministic meaning that in a given instantaneous description
1169:
6478:
5229:{\displaystyle Q\times \Sigma _{\epsilon }\times \Gamma ^{*}\longrightarrow P(Q\times \Gamma ^{*})}
6395:
6368:
4614:
3571:
There seems to be no generally used representation for PDA. Here we have depicted the instruction
3229:
3174:
2084:
1910:
896:
703:
672:
358:
7227:
7171:
4945:
A finite automaton with access to two stacks is a more powerful device, equivalent in power to a
3739:
Input string = 0011. There are various computations, depending on the moment the move from state
3632:
2939:
2487:
2481:
2019:
1660:
307:
5449:{\displaystyle \delta (q_{1},w,x_{1}x_{2}\cdot x_{m})\longrightarrow (q_{2},y_{1}y_{2}...y_{n})}
4953:
is a device which is more powerful than a pushdown automaton but less so than a Turing machine.
2663:
2569:
634:
93:
6218:
As a generalization of pushdown automata, Ginsburg, Greibach, and
Harrison (1967) investigated
5144:
4797:
3710:
The following illustrates how the above PDA computes on different input strings. The subscript
2404:{\displaystyle N(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(q,\varepsilon ,\varepsilon )}
7020:
6943:
6928:
6900:
6890:
6859:
6824:
6643:
6495:
6455:
6451:
2477:
2414:
619:{\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma \times Q\times \Gamma ^{*}}
6427:. In an existential state an APDA nondeterministically chooses the next state and accepts if
5278:
5245:
4231:
The final state is accepting, but the input is not accepted this way as it has not been read.
3837:
The final state is accepting, but the input is not accepted this way as it has not been read.
3717:
3674:
3151:
3116:
3071:
1640:
1059:
540:
515:
490:
338:
7269:
7222:
7189:
7035:
6882:
6851:
6814:
6781:
6748:
6712:
6603:
6459:
6447:
6439:
4847:
3530:
The third and fourth instructions say that, at any moment the automaton may move from state
2230:
832:
6703:
Holzer, Markus; Kutrib, Martin (2019). "Non-Recursive Trade-Offs Are "Almost
Everywhere"".
1952:
7232:
7147:
7114:
7030:
7003:
6999:
6505:
6467:
4916:
4842:
The language of strings accepted by a deterministic pushdown automaton (DPDA) is called a
2220:{\displaystyle L(M)=\{w\in \Sigma ^{*}|(q_{0},w,Z)\vdash _{M}^{*}(f,\varepsilon ,\gamma )}
1053:
In many texts the transition relation is replaced by an (equivalent) formalization, where
177:
6723:
any deterministic pushdown automaton can be converted into an equivalent finite automaton
4721:
The PDA accepts by empty stack. Its initial stack symbol is the grammar's start symbol.
4141:
Input string = 00111. Again there are various computations. None of these is accepting.
2638:
2544:
7243:
7025:
7007:
6916:
5119:
4946:
4896:
4876:
4856:
4776:
4756:
4696:
2618:
2524:
2064:
1999:
1979:
1687:
1620:
1250:
1230:
1210:
962:
942:
922:
812:
792:
465:
192:
6959:, simulator for several types of automata including nondeterministic pushdown automata
6608:
6591:
7346:
7328:
6921:
6636:
6510:
5678:
6443:
4135:
Accepting computation: ends in accepting state, while complete input has been read.
376:
17:
6886:
6481:
in the same way as nondeterministic PDA are equivalent to context-free grammars.
6240:. The class of languages accepted by deterministic, nonerasing stack automata is
2716:
The following is the formal description of the PDA which recognizes the language
7295:
7217:
7142:
6716:
238:
35:
6530:
280:. In general, if several actions are possible, then the automaton is called a
6904:
6863:
6828:
1539:
6819:
6802:
6786:
6769:
6753:
6736:
3556:
Finally, the sixth instruction says that the machine may move from state
2774:
6881:. Lecture Notes in Computer Science. Vol. 6651. pp. 345โ358.
6463:
3699:
6768:
Seymour
Ginsburg, Sheila A. Greibach and Michael A. Harrison (1967).
6735:
Seymour
Ginsburg, Sheila A. Greibach and Michael A. Harrison (1967).
6242:
6228:
1610:{\displaystyle (p,w,\beta )\in Q\times \Sigma ^{*}\times \Gamma ^{*}}
212:
6855:
1123:{\displaystyle Q\times (\Sigma \cup \{\varepsilon \})\times \Gamma }
5242:
Computation rules for a GPDA are the same as a PDA except that the
2923:{\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ Z,\ F)}
259:
It can use the top of the stack to decide which transition to take.
7258:
6801:
Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981).
4744:ฮณ also yields an equivalent nondeterministic pushdown automaton.
6972:
5057:{\displaystyle M=(Q,\ \Sigma ,\ \Gamma ,\ \delta ,\ q_{0},\ F)}
4913:
describing a regular language whose smallest DPDA has at least
4318:{\displaystyle (p,00111,Z)\vdash (p,0111,AZ)\vdash (q,0111,AZ)}
4223:{\displaystyle (p,00111,Z)\vdash (q,00111,Z)\vdash (r,00111,Z)}
262:
It can manipulate the stack as part of performing a transition.
6962:
6721:
This follows from the quoted and the stated observation that
1831:{\displaystyle (p,ax,A\gamma )\vdash _{M}(q,x,\alpha \gamma )}
1441:{\displaystyle (q,BA)\in \{(q,BA)\},(q,BA)\in \delta (p,a,A),}
29:
6533:
of bits can't be recognized by a deterministic PDA, but is a
2511:
meaning any number of consecutive steps (zero, one or more).
7327:
Each category of languages, except those marked by a , is a
6687:
John E. Hopcroft; Rajeev
Motwani; Jeffrey D. Ullman (2003).
3924:{\displaystyle (p,0011,Z)\vdash (p,011,AZ)\vdash (q,011,AZ)}
3829:{\displaystyle (p,0011,Z)\vdash (q,0011,Z)\vdash (r,0011,Z)}
134:
6689:
Introduction to
Automata Theory, Languages, and Computation
6638:
Introduction to
Automata Theory, Languages, and Computation
6956:
6354:{\displaystyle Q_{\exists }\cap Q_{\forall }=\emptyset }
153:(Clicking on each layer gets an article on that subject)
6939:
Section 2.2: Pushdown Automata, pp. 101–114.
3491:
In words, the first two instructions say that in state
452:{\displaystyle M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},Z,F)}
6629:
6627:
6625:
6623:
6621:
6619:
6585:
6583:
6581:
6470:, it can be decided by an exponential-time algorithm.
6398:
6371:
6321:
6275:
5676:
5465:
5323:
5281:
5248:
5168:
5147:
5122:
5073:
4986:
4919:
4899:
4879:
4859:
4800:
4779:
4759:
4699:
4649:
4617:
4567:
4334:
4239:
4150:
3940:
3845:
3756:
3720:
3677:
3635:
3577:
3443:
3391:
3339:
3287:
3232:
3177:
3154:
3119:
3074:
3032:
2990:
2942:
2843:
2784:
2722:
2666:
2641:
2621:
2572:
2547:
2527:
2490:
2450:
2417:
2297:
2259:
2233:
2113:
2087:
2067:
2022:
2002:
1982:
1955:
1913:
1877:
1844:
1766:
1710:
1690:
1663:
1643:
1623:
1553:
1454:
1341:
1273:
1253:
1233:
1213:
1172:
1136:
1086:
1062:
1018:
985:
965:
945:
925:
899:
861:
835:
815:
795:
739:
706:
675:
637:
563:
543:
518:
493:
468:
390:
361:
341:
310:
60:. Unsourced material may be challenged and removed.
6920:
6635:
6411:
6384:
6353:
6307:
6202:
5656:
5448:
5300:
5267:
5228:
5154:
5128:
5106:
5056:
4934:
4905:
4885:
4865:
4830:
4785:
4765:
4705:
4685:
4629:
4603:
4520:
4317:
4222:
4126:
3923:
3828:
3726:
3683:
3655:
3613:
3479:
3427:
3375:
3323:
3271:
3216:
3160:
3137:
3093:
3056:
3014:
2972:
2922:
2825:
2763:
2701:
2652:
2627:
2607:
2558:
2533:
2503:
2468:
2432:
2403:
2281:
2245:
2219:
2093:
2073:
2053:
2008:
1988:
1968:
1937:
1896:
1863:
1830:
1752:
1696:
1676:
1649:
1629:
1609:
1517:
1440:
1327:
1259:
1239:
1219:
1199:
1155:
1122:
1068:
1042:
1004:
971:
951:
931:
911:
885:
847:
821:
801:
781:
718:
687:
656:
618:
549:
524:
499:
474:
451:
367:
347:
323:
6942:Jean-Michel Autebert, Jean Berstel, Luc Boasson,
5667:Construct the following transitions for the PDA:
2016:on the input tape, thus with initial description
886:{\displaystyle a\in \Sigma \cup \{\varepsilon \}}
255:differs from a finite state machine in two ways:
6266:(APDA) is a pushdown automaton with a state set
218:The term "pushdown" refers to the fact that the
6634:John E. Hopcroft and Jeffrey D. Ullman (1979).
6308:{\displaystyle Q=Q_{\exists }\cup Q_{\forall }}
1704:on instantaneous descriptions. For instruction
1617:is called an instantaneous description (ID) of
1518:{\displaystyle ((p,a,A),\{(q,BA)\})\in \delta }
138:
2615:, and vice versa, for each pushdown automaton
1043:{\displaystyle (\Sigma \cup \{\varepsilon \})}
207:while nondeterministic ones can recognize all
6984:
6944:Context-Free Languages and Push-Down Automata
4850:, there is a size explosion problem: for any
8:
6590:John E. Hopcroft; Jeffrey D. Ullman (1967).
4604:{\displaystyle (1,\varepsilon ,A,1,\alpha )}
3168:consists of the following six instructions:
3132:
3126:
3051:
3039:
3009:
2997:
2967:
2949:
2820:
2785:
2758:
2723:
2427:
2313:
2276:
2129:
1753:{\displaystyle (p,a,A,q,\alpha )\in \delta }
1503:
1482:
1384:
1363:
1322:
1301:
1108:
1102:
1034:
1028:
880:
874:
782:{\displaystyle (p,a,A,q,\alpha )\in \delta }
585:
579:
7306:Counter-free (with aperiodic finite monoid)
5107:{\displaystyle Q,\Sigma \,,\Gamma \,,q_{0}}
7016:
6991:
6977:
6969:
6879:Computer Science โ Theory and Applications
6475:synchronized alternating pushdown automata
4977:A GPDA is formally defined as a 6-tuple:
2826:{\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}
2764:{\displaystyle \{0^{n}1^{n}\mid n\geq 0\}}
304:We use standard formal language notation:
6923:Introduction to the Theory of Computation
6818:
6785:
6752:
6607:
6466:i.e. a language is accepted by some APDA
6403:
6397:
6376:
6370:
6339:
6326:
6320:
6299:
6286:
6274:
6184:
6171:
6124:
6081:
6062:
6021:
5993:
5974:
5939:
5905:
5882:
5857:
5814:
5791:
5772:
5738:
5715:
5696:
5677:
5675:
5636:
5623:
5604:
5591:
5566:
5553:
5534:
5521:
5508:
5483:
5470:
5464:
5437:
5418:
5408:
5395:
5376:
5363:
5353:
5334:
5322:
5286:
5280:
5253:
5247:
5217:
5192:
5179:
5167:
5148:
5146:
5121:
5098:
5090:
5083:
5072:
5036:
4985:
4918:
4898:
4878:
4858:
4799:
4778:
4773:one may construct a context-free grammar
4758:
4698:
4648:
4616:
4566:
4333:
4238:
4149:
3939:
3844:
3755:
3747:is made. Only one of these is accepting.
3719:
3676:
3645:
3634:
3576:
3564:only when the stack consists of a single
3541:The fifth instruction says that in state
3503:is pushed onto the stack. Pushing symbol
3442:
3390:
3338:
3286:
3231:
3176:
3153:
3118:
3079:
3073:
3031:
2989:
2941:
2893:
2842:
2802:
2792:
2783:
2740:
2730:
2721:
2665:
2640:
2620:
2571:
2546:
2526:
2495:
2489:
2460:
2455:
2449:
2416:
2374:
2369:
2344:
2332:
2326:
2296:
2270:
2258:
2232:
2190:
2185:
2160:
2148:
2142:
2112:
2086:
2066:
2030:
2021:
2001:
1981:
1960:
1954:
1912:
1888:
1876:
1855:
1843:
1798:
1765:
1709:
1689:
1668:
1662:
1642:
1622:
1601:
1588:
1552:
1453:
1340:
1328:{\displaystyle \delta (p,a,A)=\{(q,BA)\}}
1272:
1252:
1232:
1212:
1171:
1147:
1135:
1085:
1061:
1017:
996:
984:
964:
944:
924:
898:
860:
834:
814:
794:
738:
705:
674:
642:
636:
610:
562:
542:
517:
492:
467:
428:
389:
360:
340:
315:
309:
120:Learn how and when to remove this message
6462:proved that this model is equivalent to
3698:
2773:
2282:{\displaystyle \gamma \in \Gamma ^{*}\}}
1538:
382:A PDA is formally defined as a 7-tuple:
237:
6596:Journal of Computer and System Sciences
6577:
6522:
5308:'s are now strings instead of symbols.
2635:one may construct a pushdown automaton
2541:one may construct a pushdown automaton
1207:contains all possible actions in state
7198:Linear context-free rewriting language
4686:{\displaystyle (1,a,a,1,\varepsilon )}
1897:{\displaystyle \gamma \in \Gamma ^{*}}
1005:{\displaystyle \alpha \in \Gamma ^{*}}
7123:Linear context-free rewriting systems
6705:Computing with Foresight and Industry
1267:on the input. One writes for example
7:
532:is a finite set which is called the
507:is a finite set which is called the
205:deterministic context-free languages
196:
58:adding citations to reliable sources
6725:of at most doubly-exponential size.
6473:Aizikowitz and Kaminski introduced
6435:the resulting computations accept.
5138:are defined the same way as a PDA.
4873:and for arbitrarily large integers
4844:deterministic context-free language
3480:{\displaystyle (q,\epsilon ,Z,r,Z)}
3428:{\displaystyle (q,1,A,q,\epsilon )}
3376:{\displaystyle (p,\epsilon ,A,q,A)}
3324:{\displaystyle (p,\epsilon ,Z,q,Z)}
1156:{\displaystyle Q\times \Gamma ^{*}}
809:. It has the intended meaning that
7331:of the category directly above it.
6404:
6377:
6348:
6340:
6327:
6300:
6287:
5633:
5563:
5505:
5214:
5189:
5176:
5087:
5080:
5014:
5005:
3519:(and similarly for pushing symbol
3033:
2991:
2871:
2862:
2323:
2267:
2139:
1885:
1852:
1598:
1585:
1144:
1117:
1096:
1022:
993:
919:as topmost stack symbol, may read
906:
868:
682:
607:
594:
573:
519:
494:
412:
406:
342:
312:
294:language accepted by the automaton
25:
3614:{\displaystyle (p,a,A,q,\alpha )}
2081:), or it accepts by empty stack (
1529:in this definition is essential.
331:denotes the set of finite-length
242:A diagram of a pushdown automaton
1864:{\displaystyle x\in \Sigma ^{*}}
1543:a step of the pushdown automaton
276:deterministic pushdown automaton
211:, with the former often used in
34:
6477:(SAPDA) that are equivalent to
3511:is formalized as replacing top
3057:{\displaystyle \Gamma =\{A,Z\}}
3015:{\displaystyle \Sigma =\{0,1\}}
2469:{\displaystyle \vdash _{M}^{*}}
201:Deterministic pushdown automata
45:needs additional citations for
6737:"Stack Automata and Compiling"
6642:. Reading/MA: Addison-Wesley.
6264:alternating pushdown automaton
6258:Alternating pushdown automata
6236:), which is a superset of the
6190:
6164:
6159:
6154:
6117:
6093:
6055:
6050:
6045:
6014:
5999:
5967:
5962:
5957:
5932:
5917:
5898:
5893:
5888:
5850:
5826:
5807:
5802:
5797:
5765:
5750:
5731:
5726:
5721:
5689:
5443:
5388:
5385:
5382:
5327:
5223:
5204:
5198:
5051:
4993:
4929:
4923:
4825:
4819:
4810:
4804:
4724:For a context-free grammar in
4680:
4650:
4621:
4598:
4568:
4515:
4497:
4491:
4473:
4467:
4446:
4440:
4416:
4410:
4386:
4380:
4359:
4353:
4335:
4312:
4291:
4285:
4264:
4258:
4240:
4217:
4199:
4193:
4175:
4169:
4151:
4121:
4103:
4097:
4079:
4073:
4052:
4046:
4022:
4016:
3992:
3986:
3965:
3959:
3941:
3918:
3897:
3891:
3870:
3864:
3846:
3823:
3805:
3799:
3781:
3775:
3757:
3608:
3578:
3474:
3444:
3422:
3392:
3370:
3340:
3318:
3288:
3266:
3233:
3211:
3178:
2917:
2850:
2696:
2685:
2676:
2670:
2602:
2591:
2582:
2576:
2398:
2380:
2362:
2337:
2333:
2307:
2301:
2214:
2196:
2178:
2153:
2149:
2123:
2117:
2048:
2023:
1976:with the initial stack symbol
1932:
1914:
1825:
1804:
1791:
1767:
1741:
1711:
1572:
1554:
1506:
1500:
1485:
1476:
1458:
1455:
1432:
1414:
1405:
1390:
1381:
1366:
1357:
1342:
1319:
1304:
1295:
1277:
1200:{\displaystyle \delta (p,a,A)}
1194:
1176:
1111:
1093:
1037:
1019:
770:
740:
588:
570:
446:
397:
1:
6609:10.1016/s0022-0000(67)80013-8
6887:10.1007/978-3-642-20712-9_27
6438:The model was introduced by
6412:{\displaystyle Q_{\forall }}
6385:{\displaystyle Q_{\exists }}
5456:be a transition of the GPDA
5239:is the transition function.
4753:For each pushdown automaton
4630:{\displaystyle A\to \alpha }
3272:{\displaystyle (p,0,A,p,AA)}
3217:{\displaystyle (p,0,Z,p,AZ)}
2521:For each pushdown automaton
2094:{\displaystyle \varepsilon }
1938:{\displaystyle (p,w,\beta )}
1247:on the stack, while reading
912:{\displaystyle A\in \Gamma }
719:{\displaystyle F\subseteq Q}
688:{\displaystyle Z\in \Gamma }
368:{\displaystyle \varepsilon }
166:theoretical computer science
6717:10.1007/978-3-030-22996-2_3
6592:"Nonerasing Stack Automata"
6238:context-sensitive languages
3656:{\displaystyle a;A/\alpha }
2973:{\displaystyle Q=\{p,q,r\}}
2504:{\displaystyle \vdash _{M}}
2054:{\displaystyle (q_{0},w,Z)}
1996:on the stack, and a string
1677:{\displaystyle \vdash _{M}}
324:{\displaystyle \Gamma ^{*}}
7374:
7213:Deterministic context-free
7138:Deterministic context-free
4326:No further steps possible.
3932:No further steps possible.
3703:accepting computation for
2702:{\displaystyle N(M)=L(M')}
2608:{\displaystyle L(M)=N(M')}
1657:defines the step-relation
979:, replacing it by pushing
657:{\displaystyle q_{0}\in Q}
7324:
7286:Nondeterministic pushdown
7014:
6844:SIAM Journal on Computing
5155:{\displaystyle \,\delta }
4893:, there is a PDA of size
4831:{\displaystyle N(M)=L(G)}
4693:for each terminal symbol
6770:"One-Way Stack Automata"
4951:linear bounded automaton
4736:) for each grammar rule
3148:The transition relation
2433:{\displaystyle q\in Q\}}
253:pushdown automaton (PDA)
6693:Here: Sect.6.4.3, p.249
6529:The set of even-length
5301:{\displaystyle b_{i+1}}
5268:{\displaystyle a_{i+1}}
4728:, defining (1,ฮณ) โ ฮด(1,
3727:{\displaystyle \vdash }
3684:{\displaystyle \alpha }
3161:{\displaystyle \delta }
3138:{\displaystyle F=\{r\}}
3094:{\displaystyle q_{0}=p}
1650:{\displaystyle \delta }
1130:into finite subsets of
1069:{\displaystyle \delta }
550:{\displaystyle \delta }
525:{\displaystyle \Gamma }
500:{\displaystyle \Sigma }
348:{\displaystyle \Gamma }
7353:Automata (computation)
7291:Deterministic pushdown
7167:Recursively enumerable
6563:recursively enumerable
6413:
6386:
6355:
6309:
6204:
5658:
5450:
5302:
5269:
5230:
5156:
5130:
5108:
5058:
4936:
4907:
4887:
4867:
4832:
4787:
4767:
4707:
4687:
4631:
4605:
4538:Context-free languages
4522:
4319:
4224:
4128:
3925:
3830:
3728:
3707:
3685:
3657:
3621:by an edge from state
3615:
3481:
3429:
3377:
3325:
3273:
3218:
3162:
3139:
3095:
3058:
3016:
2974:
2924:
2835:
2827:
2765:
2703:
2654:
2629:
2609:
2560:
2535:
2505:
2470:
2434:
2405:
2283:
2247:
2246:{\displaystyle f\in F}
2221:
2095:
2075:
2055:
2010:
1990:
1970:
1939:
1898:
1865:
1832:
1754:
1698:
1678:
1651:
1631:
1611:
1544:
1519:
1442:
1329:
1261:
1241:
1221:
1201:
1157:
1124:
1070:
1044:
1006:
973:
953:
939:, change the state to
933:
913:
887:
849:
848:{\displaystyle p\in Q}
823:
803:
783:
720:
689:
658:
620:
557:is a finite subset of
551:
526:
501:
476:
453:
369:
349:
325:
243:
228:nested stack automaton
209:context-free languages
191:but less capable than
146:
7358:Models of computation
6820:10.1145/322234.322243
6787:10.1145/321386.321403
6754:10.1145/321371.321385
6535:context-free language
6414:
6387:
6356:
6310:
6205:
5659:
5451:
5303:
5270:
5231:
5157:
5131:
5109:
5059:
4937:
4908:
4888:
4868:
4833:
4788:
4768:
4708:
4688:
4632:
4606:
4523:
4320:
4225:
4129:
3926:
3831:
3729:
3714:from the step symbol
3702:
3686:
3658:
3616:
3482:
3430:
3378:
3326:
3274:
3219:
3163:
3140:
3096:
3059:
3017:
2975:
2925:
2828:
2777:
2766:
2704:
2655:
2630:
2610:
2561:
2536:
2506:
2484:of the step relation
2471:
2435:
2406:
2284:
2248:
2222:
2104:Formally one defines
2096:
2076:
2056:
2011:
1991:
1971:
1969:{\displaystyle q_{0}}
1940:
1899:
1866:
1833:
1755:
1699:
1679:
1652:
1632:
1612:
1542:
1520:
1443:
1330:
1262:
1242:
1222:
1202:
1158:
1125:
1071:
1045:
1007:
974:
954:
934:
914:
888:
850:
824:
804:
784:
721:
690:
659:
621:
552:
527:
502:
477:
454:
370:
350:
326:
241:
189:finite-state machines
162:theory of computation
145:
7276:Tree stack automaton
6501:Finite-state machine
6491:Context-free grammar
6479:conjunctive grammars
6396:
6369:
6319:
6273:
5674:
5463:
5321:
5279:
5246:
5166:
5145:
5120:
5071:
4984:
4935:{\displaystyle f(n)}
4917:
4897:
4877:
4857:
4798:
4777:
4757:
4726:Greibach normal form
4697:
4647:
4615:
4565:
4544:context-free grammar
4332:
4237:
4148:
3938:
3843:
3754:
3718:
3675:
3633:
3575:
3495:any time the symbol
3441:
3389:
3337:
3285:
3230:
3175:
3152:
3117:
3072:
3030:
2988:
2940:
2841:
2782:
2720:
2664:
2639:
2619:
2570:
2545:
2525:
2488:
2448:
2415:
2295:
2257:
2231:
2111:
2085:
2065:
2020:
2000:
1980:
1953:
1911:
1875:
1842:
1764:
1760:there exists a step
1708:
1688:
1661:
1641:
1621:
1551:
1452:
1339:
1271:
1251:
1231:
1211:
1170:
1134:
1084:
1060:
1016:
983:
963:
943:
923:
897:
859:
833:
813:
793:
737:
704:
697:initial stack symbol
673:
635:
561:
541:
516:
491:
466:
388:
359:
339:
308:
248:finite-state machine
234:Informal description
150:Classes of automata
69:"Pushdown automaton"
54:improve this article
7184:range concatenation
7109:range concatenation
6664:"Pushdown Automata"
3560:to accepting state
3104:start stack symbol:
2465:
2379:
2195:
1078:transition function
789:is a transition of
628:transition relation
482:is a finite set of
18:Push down automaton
6927:. PWS Publishing.
6807:Journal of the ACM
6409:
6382:
6351:
6305:
6200:
6198:
5654:
5446:
5298:
5265:
5226:
5152:
5126:
5104:
5054:
4932:
4903:
4883:
4863:
4852:recursive function
4828:
4783:
4763:
4703:
4683:
4627:
4601:
4518:
4315:
4220:
4124:
3921:
3826:
3724:
3708:
3681:
3653:
3611:
3545:, for each symbol
3507:on top of another
3477:
3425:
3373:
3321:
3269:
3214:
3158:
3135:
3091:
3054:
3012:
2970:
2920:
2836:
2823:
2761:
2699:
2653:{\displaystyle M'}
2650:
2625:
2605:
2559:{\displaystyle M'}
2556:
2531:
2501:
2482:transitive closure
2466:
2451:
2430:
2401:
2365:
2279:
2243:
2217:
2181:
2091:
2071:
2051:
2006:
1986:
1966:
1935:
1894:
1861:
1828:
1750:
1694:
1674:
1647:
1627:
1607:
1545:
1515:
1438:
1325:
1257:
1237:
1217:
1197:
1153:
1120:
1066:
1040:
1002:
969:
949:
929:
909:
883:
845:
819:
799:
779:
716:
685:
654:
616:
547:
522:
497:
472:
449:
365:
345:
321:
244:
203:can recognize all
176:) is a type of
170:pushdown automaton
147:
7340:
7339:
7319:
7318:
7281:Embedded pushdown
7177:Context-sensitive
7102:Context-sensitive
7036:Abstract machines
7021:Chomsky hierarchy
6896:978-3-642-20711-2
6691:. Addison Wesley.
6496:Counter automaton
5129:{\displaystyle F}
5047:
5031:
5022:
5013:
5004:
4906:{\displaystyle n}
4886:{\displaystyle n}
4866:{\displaystyle f}
4848:regular languages
4786:{\displaystyle G}
4766:{\displaystyle M}
4706:{\displaystyle a}
3734:is here omitted.
3112:accepting states:
2913:
2904:
2888:
2879:
2870:
2861:
2628:{\displaystyle M}
2534:{\displaystyle M}
2074:{\displaystyle F}
2009:{\displaystyle w}
1989:{\displaystyle Z}
1697:{\displaystyle M}
1630:{\displaystyle M}
1260:{\displaystyle a}
1240:{\displaystyle A}
1220:{\displaystyle p}
972:{\displaystyle A}
952:{\displaystyle q}
932:{\displaystyle a}
822:{\displaystyle M}
802:{\displaystyle M}
475:{\displaystyle Q}
300:Formal definition
130:
129:
122:
104:
27:Type of automaton
16:(Redirected from
7365:
7335:
7332:
7296:Visibly pushdown
7270:Thread automaton
7218:Visibly pushdown
7186:
7143:Visibly pushdown
7111:
7098:(no common name)
7017:
7004:formal languages
6993:
6986:
6979:
6970:
6938:
6926:
6909:
6908:
6874:
6868:
6867:
6839:
6833:
6832:
6822:
6798:
6792:
6791:
6789:
6765:
6759:
6758:
6756:
6732:
6726:
6724:
6720:
6700:
6694:
6692:
6684:
6678:
6677:
6675:
6674:
6660:
6654:
6653:
6641:
6631:
6614:
6613:
6611:
6587:
6566:
6559:
6553:
6527:
6418:
6416:
6415:
6410:
6408:
6407:
6391:
6389:
6388:
6383:
6381:
6380:
6360:
6358:
6357:
6352:
6344:
6343:
6331:
6330:
6314:
6312:
6311:
6306:
6304:
6303:
6291:
6290:
6209:
6207:
6206:
6201:
6199:
6189:
6188:
6176:
6175:
6141:
6140:
6116:
6105:
6099:
6092:
6091:
6073:
6072:
6032:
6031:
6013:
5998:
5997:
5985:
5984:
5944:
5943:
5931:
5910:
5909:
5887:
5886:
5868:
5867:
5849:
5838:
5832:
5819:
5818:
5796:
5795:
5777:
5776:
5764:
5743:
5742:
5720:
5719:
5701:
5700:
5688:
5663:
5661:
5660:
5655:
5641:
5640:
5628:
5627:
5609:
5608:
5596:
5595:
5571:
5570:
5558:
5557:
5539:
5538:
5526:
5525:
5513:
5512:
5488:
5487:
5475:
5474:
5455:
5453:
5452:
5447:
5442:
5441:
5423:
5422:
5413:
5412:
5400:
5399:
5381:
5380:
5368:
5367:
5358:
5357:
5339:
5338:
5307:
5305:
5304:
5299:
5297:
5296:
5274:
5272:
5271:
5266:
5264:
5263:
5235:
5233:
5232:
5227:
5222:
5221:
5197:
5196:
5184:
5183:
5161:
5159:
5158:
5153:
5137:
5135:
5133:
5132:
5127:
5113:
5111:
5110:
5105:
5103:
5102:
5063:
5061:
5060:
5055:
5045:
5041:
5040:
5029:
5020:
5011:
5002:
4941:
4939:
4938:
4933:
4912:
4910:
4909:
4904:
4892:
4890:
4889:
4884:
4872:
4870:
4869:
4864:
4839:
4837:
4835:
4834:
4829:
4792:
4790:
4789:
4784:
4772:
4770:
4769:
4764:
4712:
4710:
4709:
4704:
4692:
4690:
4689:
4684:
4636:
4634:
4633:
4628:
4610:
4608:
4607:
4602:
4527:
4525:
4524:
4519:
4324:
4322:
4321:
4316:
4229:
4227:
4226:
4221:
4133:
4131:
4130:
4125:
3930:
3928:
3927:
3922:
3835:
3833:
3832:
3827:
3746:
3742:
3733:
3731:
3730:
3725:
3713:
3706:
3690:
3688:
3687:
3682:
3670:
3666:
3662:
3660:
3659:
3654:
3649:
3628:
3624:
3620:
3618:
3617:
3612:
3567:
3563:
3559:
3552:
3548:
3544:
3537:
3533:
3526:
3522:
3518:
3514:
3510:
3506:
3502:
3498:
3494:
3486:
3484:
3483:
3478:
3434:
3432:
3431:
3426:
3382:
3380:
3379:
3374:
3330:
3328:
3327:
3322:
3278:
3276:
3275:
3270:
3223:
3221:
3220:
3215:
3167:
3165:
3164:
3159:
3144:
3142:
3141:
3136:
3108:
3100:
3098:
3097:
3092:
3084:
3083:
3063:
3061:
3060:
3055:
3021:
3019:
3018:
3013:
2979:
2977:
2976:
2971:
2929:
2927:
2926:
2921:
2911:
2902:
2898:
2897:
2886:
2877:
2868:
2859:
2834:(by final state)
2832:
2830:
2829:
2824:
2807:
2806:
2797:
2796:
2771:by final state:
2770:
2768:
2767:
2762:
2745:
2744:
2735:
2734:
2708:
2706:
2705:
2700:
2695:
2659:
2657:
2656:
2651:
2649:
2634:
2632:
2631:
2626:
2614:
2612:
2611:
2606:
2601:
2565:
2563:
2562:
2557:
2555:
2540:
2538:
2537:
2532:
2510:
2508:
2507:
2502:
2500:
2499:
2475:
2473:
2472:
2467:
2464:
2459:
2439:
2437:
2436:
2431:
2410:
2408:
2407:
2402:
2378:
2373:
2349:
2348:
2336:
2331:
2330:
2288:
2286:
2285:
2280:
2275:
2274:
2252:
2250:
2249:
2244:
2226:
2224:
2223:
2218:
2194:
2189:
2165:
2164:
2152:
2147:
2146:
2100:
2098:
2097:
2092:
2080:
2078:
2077:
2072:
2060:
2058:
2057:
2052:
2035:
2034:
2015:
2013:
2012:
2007:
1995:
1993:
1992:
1987:
1975:
1973:
1972:
1967:
1965:
1964:
1944:
1942:
1941:
1936:
1903:
1901:
1900:
1895:
1893:
1892:
1870:
1868:
1867:
1862:
1860:
1859:
1837:
1835:
1834:
1829:
1803:
1802:
1759:
1757:
1756:
1751:
1703:
1701:
1700:
1695:
1683:
1681:
1680:
1675:
1673:
1672:
1656:
1654:
1653:
1648:
1636:
1634:
1633:
1628:
1616:
1614:
1613:
1608:
1606:
1605:
1593:
1592:
1524:
1522:
1521:
1516:
1447:
1445:
1444:
1439:
1334:
1332:
1331:
1326:
1266:
1264:
1263:
1258:
1246:
1244:
1243:
1238:
1226:
1224:
1223:
1218:
1206:
1204:
1203:
1198:
1162:
1160:
1159:
1154:
1152:
1151:
1129:
1127:
1126:
1121:
1075:
1073:
1072:
1067:
1049:
1047:
1046:
1041:
1011:
1009:
1008:
1003:
1001:
1000:
978:
976:
975:
970:
958:
956:
955:
950:
938:
936:
935:
930:
918:
916:
915:
910:
892:
890:
889:
884:
854:
852:
851:
846:
828:
826:
825:
820:
808:
806:
805:
800:
788:
786:
785:
780:
728:accepting states
725:
723:
722:
717:
694:
692:
691:
686:
663:
661:
660:
655:
647:
646:
625:
623:
622:
617:
615:
614:
556:
554:
553:
548:
531:
529:
528:
523:
506:
504:
503:
498:
481:
479:
478:
473:
458:
456:
455:
450:
433:
432:
374:
372:
371:
366:
354:
352:
351:
346:
330:
328:
327:
322:
320:
319:
286:nondeterministic
154:
137:
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
7373:
7372:
7368:
7367:
7366:
7364:
7363:
7362:
7343:
7342:
7341:
7336:
7333:
7326:
7320:
7315:
7237:
7181:
7160:
7106:
7087:
7010:
7008:formal grammars
7000:Automata theory
6997:
6953:
6935:
6915:
6912:
6897:
6876:
6875:
6871:
6856:10.1137/0213010
6841:
6840:
6836:
6800:
6799:
6795:
6767:
6766:
6762:
6734:
6733:
6729:
6722:
6702:
6701:
6697:
6686:
6685:
6681:
6672:
6670:
6662:
6661:
6657:
6650:
6633:
6632:
6617:
6589:
6588:
6579:
6575:
6570:
6569:
6560:
6556:
6528:
6524:
6519:
6506:Queue automaton
6487:
6468:if, and only if
6399:
6394:
6393:
6372:
6367:
6366:
6335:
6322:
6317:
6316:
6295:
6282:
6271:
6270:
6260:
6216:
6197:
6196:
6180:
6167:
6162:
6157:
6120:
6109:
6106:
6104:
6097:
6096:
6077:
6058:
6053:
6048:
6017:
6006:
6003:
6002:
5989:
5970:
5965:
5960:
5935:
5924:
5921:
5920:
5901:
5896:
5891:
5878:
5853:
5842:
5839:
5837:
5830:
5829:
5810:
5805:
5800:
5787:
5768:
5757:
5754:
5753:
5734:
5729:
5724:
5711:
5692:
5681:
5672:
5671:
5632:
5619:
5600:
5587:
5562:
5549:
5530:
5517:
5504:
5479:
5466:
5461:
5460:
5433:
5414:
5404:
5391:
5372:
5359:
5349:
5330:
5319:
5318:
5282:
5277:
5276:
5249:
5244:
5243:
5213:
5188:
5175:
5164:
5163:
5143:
5142:
5118:
5117:
5115:
5094:
5069:
5068:
5032:
4982:
4981:
4972:
4959:
4957:Turing machines
4915:
4914:
4895:
4894:
4875:
4874:
4855:
4854:
4796:
4795:
4794:
4775:
4774:
4755:
4754:
4695:
4694:
4645:
4644:
4613:
4612:
4563:
4562:
4540:
4535:
4532:
4528:
4330:
4329:
4325:
4235:
4234:
4230:
4146:
4145:
4138:
4134:
3936:
3935:
3931:
3841:
3840:
3836:
3752:
3751:
3744:
3740:
3716:
3715:
3711:
3704:
3697:
3673:
3672:
3668:
3664:
3631:
3630:
3626:
3622:
3573:
3572:
3565:
3561:
3557:
3550:
3546:
3542:
3535:
3531:
3524:
3520:
3516:
3512:
3508:
3504:
3500:
3496:
3492:
3439:
3438:
3387:
3386:
3335:
3334:
3283:
3282:
3228:
3227:
3173:
3172:
3150:
3149:
3115:
3114:
3106:
3075:
3070:
3069:
3028:
3027:
3025:stack alphabet:
2986:
2985:
2983:input alphabet:
2938:
2937:
2889:
2839:
2838:
2833:
2798:
2788:
2780:
2779:
2736:
2726:
2718:
2717:
2714:
2688:
2662:
2661:
2642:
2637:
2636:
2617:
2616:
2594:
2568:
2567:
2548:
2543:
2542:
2523:
2522:
2491:
2486:
2485:
2476:represents the
2446:
2445:
2413:
2412:
2340:
2322:
2293:
2292:
2266:
2255:
2254:
2229:
2228:
2156:
2138:
2109:
2108:
2083:
2082:
2063:
2062:
2026:
2018:
2017:
1998:
1997:
1978:
1977:
1956:
1951:
1950:
1909:
1908:
1884:
1873:
1872:
1851:
1840:
1839:
1794:
1762:
1761:
1706:
1705:
1686:
1685:
1664:
1659:
1658:
1639:
1638:
1619:
1618:
1597:
1584:
1549:
1548:
1450:
1449:
1337:
1336:
1335:precisely when
1269:
1268:
1249:
1248:
1229:
1228:
1209:
1208:
1168:
1167:
1143:
1132:
1131:
1082:
1081:
1058:
1057:
1014:
1013:
992:
981:
980:
961:
960:
941:
940:
921:
920:
895:
894:
857:
856:
855:, on the input
831:
830:
811:
810:
791:
790:
735:
734:
702:
701:
671:
670:
638:
633:
632:
606:
559:
558:
539:
538:
514:
513:
489:
488:
464:
463:
424:
386:
385:
357:
356:
337:
336:
311:
306:
305:
302:
236:
224:stack automaton
193:Turing machines
180:that employs a
158:
157:
156:
155:
152:
148:
144:
135:
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
7371:
7369:
7361:
7360:
7355:
7345:
7344:
7338:
7337:
7325:
7322:
7321:
7317:
7316:
7314:
7313:
7311:Acyclic finite
7308:
7303:
7298:
7293:
7288:
7283:
7278:
7272:
7267:
7262:
7261:Turing Machine
7256:
7254:Linear-bounded
7251:
7246:
7244:Turing machine
7240:
7238:
7236:
7235:
7230:
7225:
7220:
7215:
7210:
7205:
7203:Tree-adjoining
7200:
7195:
7192:
7187:
7179:
7174:
7169:
7163:
7161:
7159:
7158:
7153:
7150:
7145:
7140:
7135:
7130:
7128:Tree-adjoining
7125:
7120:
7117:
7112:
7104:
7099:
7096:
7090:
7088:
7086:
7085:
7082:
7079:
7076:
7073:
7070:
7067:
7064:
7061:
7058:
7055:
7052:
7049:
7046:
7042:
7039:
7038:
7033:
7028:
7023:
7015:
7012:
7011:
6998:
6996:
6995:
6988:
6981:
6973:
6967:
6966:
6960:
6952:
6951:External links
6949:
6948:
6947:
6940:
6933:
6917:Michael Sipser
6911:
6910:
6895:
6869:
6850:(1): 135โ155.
6834:
6813:(1): 114โ133.
6793:
6780:(2): 389โ418.
6760:
6747:(1): 172โ201.
6727:
6695:
6679:
6668:www.cs.odu.edu
6655:
6648:
6615:
6602:(2): 166โ186.
6576:
6574:
6571:
6568:
6567:
6554:
6521:
6520:
6518:
6515:
6514:
6513:
6508:
6503:
6498:
6493:
6486:
6483:
6406:
6402:
6379:
6375:
6363:
6362:
6350:
6347:
6342:
6338:
6334:
6329:
6325:
6302:
6298:
6294:
6289:
6285:
6281:
6278:
6259:
6256:
6220:stack automata
6215:
6214:Stack automata
6212:
6211:
6210:
6195:
6192:
6187:
6183:
6179:
6174:
6170:
6166:
6163:
6161:
6158:
6156:
6153:
6150:
6147:
6144:
6139:
6136:
6133:
6130:
6127:
6123:
6119:
6115:
6112:
6108:
6107:
6103:
6100:
6098:
6095:
6090:
6087:
6084:
6080:
6076:
6071:
6068:
6065:
6061:
6057:
6054:
6052:
6049:
6047:
6044:
6041:
6038:
6035:
6030:
6027:
6024:
6020:
6016:
6012:
6009:
6005:
6004:
6001:
5996:
5992:
5988:
5983:
5980:
5977:
5973:
5969:
5966:
5964:
5961:
5959:
5956:
5953:
5950:
5947:
5942:
5938:
5934:
5930:
5927:
5923:
5922:
5919:
5916:
5913:
5908:
5904:
5900:
5897:
5895:
5892:
5890:
5885:
5881:
5877:
5874:
5871:
5866:
5863:
5860:
5856:
5852:
5848:
5845:
5841:
5840:
5836:
5833:
5831:
5828:
5825:
5822:
5817:
5813:
5809:
5806:
5804:
5801:
5799:
5794:
5790:
5786:
5783:
5780:
5775:
5771:
5767:
5763:
5760:
5756:
5755:
5752:
5749:
5746:
5741:
5737:
5733:
5730:
5728:
5725:
5723:
5718:
5714:
5710:
5707:
5704:
5699:
5695:
5691:
5687:
5684:
5680:
5679:
5653:
5650:
5647:
5644:
5639:
5635:
5631:
5626:
5622:
5618:
5615:
5612:
5607:
5603:
5599:
5594:
5590:
5586:
5583:
5580:
5577:
5574:
5569:
5565:
5561:
5556:
5552:
5548:
5545:
5542:
5537:
5533:
5529:
5524:
5520:
5516:
5511:
5507:
5503:
5500:
5497:
5494:
5491:
5486:
5482:
5478:
5473:
5469:
5445:
5440:
5436:
5432:
5429:
5426:
5421:
5417:
5411:
5407:
5403:
5398:
5394:
5390:
5387:
5384:
5379:
5375:
5371:
5366:
5362:
5356:
5352:
5348:
5345:
5342:
5337:
5333:
5329:
5326:
5295:
5292:
5289:
5285:
5262:
5259:
5256:
5252:
5237:
5236:
5225:
5220:
5216:
5212:
5209:
5206:
5203:
5200:
5195:
5191:
5187:
5182:
5178:
5174:
5171:
5151:
5125:
5101:
5097:
5093:
5089:
5086:
5082:
5079:
5076:
5065:
5064:
5053:
5050:
5044:
5039:
5035:
5028:
5025:
5019:
5016:
5010:
5007:
5001:
4998:
4995:
4992:
4989:
4971:
4970:Generalization
4968:
4958:
4955:
4947:Turing machine
4931:
4928:
4925:
4922:
4902:
4882:
4862:
4827:
4824:
4821:
4818:
4815:
4812:
4809:
4806:
4803:
4782:
4762:
4719:
4718:
4702:
4682:
4679:
4676:
4673:
4670:
4667:
4664:
4661:
4658:
4655:
4652:
4642:
4626:
4623:
4620:
4611:for each rule
4600:
4597:
4594:
4591:
4588:
4585:
4582:
4579:
4576:
4573:
4570:
4539:
4536:
4534:
4533:
4531:
4530:
4517:
4514:
4511:
4508:
4505:
4502:
4499:
4496:
4493:
4490:
4487:
4484:
4481:
4478:
4475:
4472:
4469:
4466:
4463:
4460:
4457:
4454:
4451:
4448:
4445:
4442:
4439:
4436:
4433:
4430:
4427:
4424:
4421:
4418:
4415:
4412:
4409:
4406:
4403:
4400:
4397:
4394:
4391:
4388:
4385:
4382:
4379:
4376:
4373:
4370:
4367:
4364:
4361:
4358:
4355:
4352:
4349:
4346:
4343:
4340:
4337:
4327:
4314:
4311:
4308:
4305:
4302:
4299:
4296:
4293:
4290:
4287:
4284:
4281:
4278:
4275:
4272:
4269:
4266:
4263:
4260:
4257:
4254:
4251:
4248:
4245:
4242:
4232:
4219:
4216:
4213:
4210:
4207:
4204:
4201:
4198:
4195:
4192:
4189:
4186:
4183:
4180:
4177:
4174:
4171:
4168:
4165:
4162:
4159:
4156:
4153:
4142:
4139:
4137:
4136:
4123:
4120:
4117:
4114:
4111:
4108:
4105:
4102:
4099:
4096:
4093:
4090:
4087:
4084:
4081:
4078:
4075:
4072:
4069:
4066:
4063:
4060:
4057:
4054:
4051:
4048:
4045:
4042:
4039:
4036:
4033:
4030:
4027:
4024:
4021:
4018:
4015:
4012:
4009:
4006:
4003:
4000:
3997:
3994:
3991:
3988:
3985:
3982:
3979:
3976:
3973:
3970:
3967:
3964:
3961:
3958:
3955:
3952:
3949:
3946:
3943:
3933:
3920:
3917:
3914:
3911:
3908:
3905:
3902:
3899:
3896:
3893:
3890:
3887:
3884:
3881:
3878:
3875:
3872:
3869:
3866:
3863:
3860:
3857:
3854:
3851:
3848:
3838:
3825:
3822:
3819:
3816:
3813:
3810:
3807:
3804:
3801:
3798:
3795:
3792:
3789:
3786:
3783:
3780:
3777:
3774:
3771:
3768:
3765:
3762:
3759:
3748:
3736:
3723:
3696:
3693:
3680:
3652:
3648:
3644:
3641:
3638:
3610:
3607:
3604:
3601:
3598:
3595:
3592:
3589:
3586:
3583:
3580:
3489:
3488:
3476:
3473:
3470:
3467:
3464:
3461:
3458:
3455:
3452:
3449:
3446:
3436:
3424:
3421:
3418:
3415:
3412:
3409:
3406:
3403:
3400:
3397:
3394:
3384:
3372:
3369:
3366:
3363:
3360:
3357:
3354:
3351:
3348:
3345:
3342:
3332:
3320:
3317:
3314:
3311:
3308:
3305:
3302:
3299:
3296:
3293:
3290:
3280:
3268:
3265:
3262:
3259:
3256:
3253:
3250:
3247:
3244:
3241:
3238:
3235:
3225:
3213:
3210:
3207:
3204:
3201:
3198:
3195:
3192:
3189:
3186:
3183:
3180:
3157:
3146:
3145:
3134:
3131:
3128:
3125:
3122:
3109:
3101:
3090:
3087:
3082:
3078:
3064:
3053:
3050:
3047:
3044:
3041:
3038:
3035:
3022:
3011:
3008:
3005:
3002:
2999:
2996:
2993:
2980:
2969:
2966:
2963:
2960:
2957:
2954:
2951:
2948:
2945:
2919:
2916:
2910:
2907:
2901:
2896:
2892:
2885:
2882:
2876:
2873:
2867:
2864:
2858:
2855:
2852:
2849:
2846:
2822:
2819:
2816:
2813:
2810:
2805:
2801:
2795:
2791:
2787:
2760:
2757:
2754:
2751:
2748:
2743:
2739:
2733:
2729:
2725:
2713:
2710:
2698:
2694:
2691:
2687:
2684:
2681:
2678:
2675:
2672:
2669:
2648:
2645:
2624:
2604:
2600:
2597:
2593:
2590:
2587:
2584:
2581:
2578:
2575:
2554:
2551:
2530:
2515:of languages.
2498:
2494:
2463:
2458:
2454:
2442:
2441:
2429:
2426:
2423:
2420:
2400:
2397:
2394:
2391:
2388:
2385:
2382:
2377:
2372:
2368:
2364:
2361:
2358:
2355:
2352:
2347:
2343:
2339:
2335:
2329:
2325:
2321:
2318:
2315:
2312:
2309:
2306:
2303:
2300:
2290:
2278:
2273:
2269:
2265:
2262:
2242:
2239:
2236:
2216:
2213:
2210:
2207:
2204:
2201:
2198:
2193:
2188:
2184:
2180:
2177:
2174:
2171:
2168:
2163:
2159:
2155:
2151:
2145:
2141:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2090:
2070:
2050:
2047:
2044:
2041:
2038:
2033:
2029:
2025:
2005:
1985:
1963:
1959:
1934:
1931:
1928:
1925:
1922:
1919:
1916:
1891:
1887:
1883:
1880:
1858:
1854:
1850:
1847:
1827:
1824:
1821:
1818:
1815:
1812:
1809:
1806:
1801:
1797:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1749:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1719:
1716:
1713:
1693:
1671:
1667:
1646:
1626:
1604:
1600:
1596:
1591:
1587:
1583:
1580:
1577:
1574:
1571:
1568:
1565:
1562:
1559:
1556:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1487:
1484:
1481:
1478:
1475:
1472:
1469:
1466:
1463:
1460:
1457:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1413:
1410:
1407:
1404:
1401:
1398:
1395:
1392:
1389:
1386:
1383:
1380:
1377:
1374:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1350:
1347:
1344:
1324:
1321:
1318:
1315:
1312:
1309:
1306:
1303:
1300:
1297:
1294:
1291:
1288:
1285:
1282:
1279:
1276:
1256:
1236:
1216:
1196:
1193:
1190:
1187:
1184:
1181:
1178:
1175:
1164:
1163:
1150:
1146:
1142:
1139:
1119:
1116:
1113:
1110:
1107:
1104:
1101:
1098:
1095:
1092:
1089:
1065:
1039:
1036:
1033:
1030:
1027:
1024:
1021:
999:
995:
991:
988:
968:
948:
928:
908:
905:
902:
882:
879:
876:
873:
870:
867:
864:
844:
841:
838:
818:
798:
778:
775:
772:
769:
766:
763:
760:
757:
754:
751:
748:
745:
742:
731:
730:
726:is the set of
715:
712:
709:
699:
684:
681:
678:
668:
653:
650:
645:
641:
630:
613:
609:
605:
602:
599:
596:
593:
590:
587:
584:
581:
578:
575:
572:
569:
566:
546:
536:
534:stack alphabet
521:
511:
509:input alphabet
496:
486:
471:
448:
445:
442:
439:
436:
431:
427:
423:
420:
417:
414:
411:
408:
405:
402:
399:
396:
393:
364:
344:
335:over alphabet
318:
314:
301:
298:
264:
263:
260:
235:
232:
164:, a branch of
151:
149:
133:
132:
131:
128:
127:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
7370:
7359:
7356:
7354:
7351:
7350:
7348:
7330:
7329:proper subset
7323:
7312:
7309:
7307:
7304:
7302:
7299:
7297:
7294:
7292:
7289:
7287:
7284:
7282:
7279:
7277:
7273:
7271:
7268:
7266:
7263:
7260:
7257:
7255:
7252:
7250:
7247:
7245:
7242:
7241:
7239:
7234:
7231:
7229:
7226:
7224:
7221:
7219:
7216:
7214:
7211:
7209:
7206:
7204:
7201:
7199:
7196:
7193:
7191:
7188:
7185:
7180:
7178:
7175:
7173:
7170:
7168:
7165:
7164:
7162:
7157:
7156:Non-recursive
7154:
7151:
7149:
7146:
7144:
7141:
7139:
7136:
7134:
7131:
7129:
7126:
7124:
7121:
7118:
7116:
7113:
7110:
7105:
7103:
7100:
7097:
7095:
7092:
7091:
7089:
7083:
7080:
7077:
7074:
7071:
7068:
7065:
7062:
7059:
7056:
7053:
7050:
7047:
7044:
7043:
7041:
7040:
7037:
7034:
7032:
7029:
7027:
7024:
7022:
7019:
7018:
7013:
7009:
7005:
7001:
6994:
6989:
6987:
6982:
6980:
6975:
6974:
6971:
6964:
6961:
6958:
6955:
6954:
6950:
6945:
6941:
6936:
6934:0-534-94728-X
6930:
6925:
6924:
6918:
6914:
6913:
6906:
6902:
6898:
6892:
6888:
6884:
6880:
6873:
6870:
6865:
6861:
6857:
6853:
6849:
6845:
6838:
6835:
6830:
6826:
6821:
6816:
6812:
6808:
6804:
6803:"Alternation"
6797:
6794:
6788:
6783:
6779:
6775:
6771:
6764:
6761:
6755:
6750:
6746:
6742:
6738:
6731:
6728:
6718:
6714:
6710:
6706:
6699:
6696:
6690:
6683:
6680:
6669:
6665:
6659:
6656:
6651:
6649:0-201-02988-X
6645:
6640:
6639:
6630:
6628:
6626:
6624:
6622:
6620:
6616:
6610:
6605:
6601:
6597:
6593:
6586:
6584:
6582:
6578:
6572:
6564:
6558:
6555:
6551:
6547:
6543:
6540:
6536:
6532:
6526:
6523:
6516:
6512:
6511:Stack machine
6509:
6507:
6504:
6502:
6499:
6497:
6494:
6492:
6489:
6488:
6484:
6482:
6480:
6476:
6471:
6469:
6465:
6461:
6457:
6453:
6449:
6445:
6441:
6436:
6434:
6430:
6426:
6422:
6400:
6373:
6345:
6336:
6332:
6323:
6296:
6292:
6283:
6279:
6276:
6269:
6268:
6267:
6265:
6257:
6255:
6253:
6249:
6245:
6244:
6239:
6235:
6231:
6230:
6225:
6221:
6213:
6193:
6185:
6181:
6177:
6172:
6168:
6151:
6148:
6145:
6142:
6137:
6134:
6131:
6128:
6125:
6121:
6113:
6110:
6101:
6088:
6085:
6082:
6078:
6074:
6069:
6066:
6063:
6059:
6042:
6039:
6036:
6033:
6028:
6025:
6022:
6018:
6010:
6007:
5994:
5990:
5986:
5981:
5978:
5975:
5971:
5954:
5951:
5948:
5945:
5940:
5936:
5928:
5925:
5914:
5911:
5906:
5902:
5883:
5879:
5875:
5872:
5869:
5864:
5861:
5858:
5854:
5846:
5843:
5834:
5823:
5820:
5815:
5811:
5792:
5788:
5784:
5781:
5778:
5773:
5769:
5761:
5758:
5747:
5744:
5739:
5735:
5716:
5712:
5708:
5705:
5702:
5697:
5693:
5685:
5682:
5670:
5669:
5668:
5665:
5651:
5648:
5645:
5642:
5637:
5629:
5624:
5620:
5616:
5613:
5610:
5605:
5601:
5597:
5592:
5588:
5584:
5581:
5578:
5575:
5572:
5567:
5559:
5554:
5550:
5546:
5543:
5540:
5535:
5531:
5527:
5522:
5518:
5514:
5509:
5501:
5498:
5495:
5492:
5489:
5484:
5480:
5476:
5471:
5467:
5457:
5438:
5434:
5430:
5427:
5424:
5419:
5415:
5409:
5405:
5401:
5396:
5392:
5377:
5373:
5369:
5364:
5360:
5354:
5350:
5346:
5343:
5340:
5335:
5331:
5324:
5315:
5312:
5309:
5293:
5290:
5287:
5283:
5260:
5257:
5254:
5250:
5240:
5218:
5210:
5207:
5201:
5193:
5185:
5180:
5172:
5169:
5149:
5141:
5140:
5139:
5123:
5099:
5095:
5091:
5084:
5077:
5074:
5048:
5042:
5037:
5033:
5026:
5023:
5017:
5008:
4999:
4996:
4990:
4987:
4980:
4979:
4978:
4975:
4969:
4967:
4963:
4956:
4954:
4952:
4948:
4943:
4926:
4920:
4900:
4880:
4860:
4853:
4849:
4845:
4840:
4822:
4816:
4813:
4807:
4801:
4780:
4760:
4752:
4748:
4745:
4743:
4739:
4735:
4731:
4727:
4722:
4716:
4700:
4677:
4674:
4671:
4668:
4665:
4662:
4659:
4656:
4653:
4643:
4640:
4624:
4618:
4595:
4592:
4589:
4586:
4583:
4580:
4577:
4574:
4571:
4561:
4560:
4559:
4556:
4554:
4550:
4545:
4537:
4512:
4509:
4506:
4503:
4500:
4494:
4488:
4485:
4482:
4479:
4476:
4470:
4464:
4461:
4458:
4455:
4452:
4449:
4443:
4437:
4434:
4431:
4428:
4425:
4422:
4419:
4413:
4407:
4404:
4401:
4398:
4395:
4392:
4389:
4383:
4377:
4374:
4371:
4368:
4365:
4362:
4356:
4350:
4347:
4344:
4341:
4338:
4328:
4309:
4306:
4303:
4300:
4297:
4294:
4288:
4282:
4279:
4276:
4273:
4270:
4267:
4261:
4255:
4252:
4249:
4246:
4243:
4233:
4214:
4211:
4208:
4205:
4202:
4196:
4190:
4187:
4184:
4181:
4178:
4172:
4166:
4163:
4160:
4157:
4154:
4144:
4143:
4140:
4118:
4115:
4112:
4109:
4106:
4100:
4094:
4091:
4088:
4085:
4082:
4076:
4070:
4067:
4064:
4061:
4058:
4055:
4049:
4043:
4040:
4037:
4034:
4031:
4028:
4025:
4019:
4013:
4010:
4007:
4004:
4001:
3998:
3995:
3989:
3983:
3980:
3977:
3974:
3971:
3968:
3962:
3956:
3953:
3950:
3947:
3944:
3934:
3915:
3912:
3909:
3906:
3903:
3900:
3894:
3888:
3885:
3882:
3879:
3876:
3873:
3867:
3861:
3858:
3855:
3852:
3849:
3839:
3820:
3817:
3814:
3811:
3808:
3802:
3796:
3793:
3790:
3787:
3784:
3778:
3772:
3769:
3766:
3763:
3760:
3750:
3749:
3738:
3737:
3735:
3721:
3701:
3694:
3692:
3678:
3650:
3646:
3642:
3639:
3636:
3629:labelled by
3605:
3602:
3599:
3596:
3593:
3590:
3587:
3584:
3581:
3569:
3554:
3539:
3528:
3499:is read, one
3471:
3468:
3465:
3462:
3459:
3456:
3453:
3450:
3447:
3437:
3419:
3416:
3413:
3410:
3407:
3404:
3401:
3398:
3395:
3385:
3367:
3364:
3361:
3358:
3355:
3352:
3349:
3346:
3343:
3333:
3315:
3312:
3309:
3306:
3303:
3300:
3297:
3294:
3291:
3281:
3263:
3260:
3257:
3254:
3251:
3248:
3245:
3242:
3239:
3236:
3226:
3208:
3205:
3202:
3199:
3196:
3193:
3190:
3187:
3184:
3181:
3171:
3170:
3169:
3155:
3129:
3123:
3120:
3113:
3110:
3105:
3102:
3088:
3085:
3080:
3076:
3068:
3065:
3048:
3045:
3042:
3036:
3026:
3023:
3006:
3003:
3000:
2994:
2984:
2981:
2964:
2961:
2958:
2955:
2952:
2946:
2943:
2936:
2933:
2932:
2931:
2914:
2908:
2905:
2899:
2894:
2890:
2883:
2880:
2874:
2865:
2856:
2853:
2847:
2844:
2817:
2814:
2811:
2808:
2803:
2799:
2793:
2789:
2776:
2772:
2755:
2752:
2749:
2746:
2741:
2737:
2731:
2727:
2711:
2709:
2692:
2689:
2682:
2679:
2673:
2667:
2646:
2643:
2622:
2598:
2595:
2588:
2585:
2579:
2573:
2552:
2549:
2528:
2520:
2516:
2512:
2496:
2492:
2483:
2479:
2461:
2456:
2452:
2440:(empty stack)
2424:
2421:
2418:
2395:
2392:
2389:
2386:
2383:
2375:
2370:
2366:
2359:
2356:
2353:
2350:
2345:
2341:
2327:
2319:
2316:
2310:
2304:
2298:
2291:
2289:(final state)
2271:
2263:
2260:
2240:
2237:
2234:
2211:
2208:
2205:
2202:
2199:
2191:
2186:
2182:
2175:
2172:
2169:
2166:
2161:
2157:
2143:
2135:
2132:
2126:
2120:
2114:
2107:
2106:
2105:
2102:
2088:
2068:
2045:
2042:
2039:
2036:
2031:
2027:
2003:
1983:
1961:
1957:
1947:
1929:
1926:
1923:
1920:
1917:
1905:
1889:
1881:
1878:
1856:
1848:
1845:
1822:
1819:
1816:
1813:
1810:
1807:
1799:
1795:
1788:
1785:
1782:
1779:
1776:
1773:
1770:
1747:
1744:
1738:
1735:
1732:
1729:
1726:
1723:
1720:
1717:
1714:
1691:
1669:
1665:
1644:
1624:
1602:
1594:
1589:
1581:
1578:
1575:
1569:
1566:
1563:
1560:
1557:
1541:
1537:
1536:
1535:
1530:
1528:
1512:
1509:
1497:
1494:
1491:
1488:
1479:
1473:
1470:
1467:
1464:
1461:
1435:
1429:
1426:
1423:
1420:
1417:
1411:
1408:
1402:
1399:
1396:
1393:
1387:
1378:
1375:
1372:
1369:
1360:
1354:
1351:
1348:
1345:
1316:
1313:
1310:
1307:
1298:
1292:
1289:
1286:
1283:
1280:
1274:
1254:
1234:
1214:
1191:
1188:
1185:
1182:
1179:
1173:
1148:
1140:
1137:
1114:
1105:
1099:
1090:
1087:
1079:
1063:
1056:
1055:
1054:
1051:
1031:
1025:
997:
989:
986:
966:
946:
926:
903:
900:
877:
871:
865:
862:
842:
839:
836:
816:
796:
776:
773:
767:
764:
761:
758:
755:
752:
749:
746:
743:
729:
713:
710:
707:
700:
698:
679:
676:
669:
667:
651:
648:
643:
639:
631:
629:
611:
603:
600:
597:
591:
582:
576:
567:
564:
544:
537:
535:
512:
510:
487:
485:
469:
462:
461:
460:
443:
440:
437:
434:
429:
425:
421:
418:
415:
409:
403:
400:
394:
391:
383:
380:
378:
362:
334:
316:
299:
297:
295:
291:
287:
283:
279:
277:
271:
268:
261:
258:
257:
256:
254:
249:
240:
233:
231:
229:
225:
221:
216:
214:
210:
206:
202:
198:
194:
190:
185:
183:
179:
175:
171:
167:
163:
124:
121:
113:
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: โ
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
7285:
7265:Nested stack
7208:Context-free
7133:Context-free
7094:Unrestricted
6922:
6878:
6872:
6847:
6843:
6837:
6810:
6806:
6796:
6777:
6773:
6763:
6744:
6740:
6730:
6708:
6704:
6698:
6688:
6682:
6671:. Retrieved
6667:
6658:
6637:
6599:
6595:
6565:) languages.
6557:
6549:
6545:
6541:
6525:
6474:
6472:
6437:
6432:
6429:at least one
6428:
6424:
6420:
6364:
6263:
6261:
6251:
6247:
6241:
6233:
6227:
6223:
6219:
6217:
5666:
5458:
5316:
5313:
5310:
5241:
5238:
5066:
4976:
4973:
4964:
4960:
4944:
4841:
4750:
4749:
4746:
4741:
4737:
4733:
4729:
4723:
4720:
4714:
4638:
4557:
4552:
4548:
4541:
3709:
3570:
3555:
3540:
3529:
3523:on top of a
3490:
3147:
3111:
3103:
3067:start state:
3066:
3024:
2982:
2934:
2837:
2715:
2518:
2517:
2513:
2443:
2103:
1948:
1906:
1838:, for every
1546:
1534:Computations
1533:
1532:
1531:
1526:
1525:. Note that
1165:
1077:
1052:
732:
727:
696:
665:
627:
533:
508:
483:
384:
381:
377:empty string
375:denotes the
303:
293:
289:
285:
281:
274:
272:
269:
265:
252:
245:
223:
217:
186:
173:
169:
159:
116:
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
7274:restricted
6537:, with the
6531:palindromes
6421:existential
6419:are called
3695:Explanation
3553:is popped.
829:, in state
733:An element
666:start state
7347:Categories
6673:2024-04-07
6573:References
6460:Stockmeyer
6448:Stockmeyer
6365:States in
6224:nonerasing
4793:such that
3667:; replace
3549:read, one
2660:such that
2566:such that
1871:and every
1080:, mapping
110:April 2022
80:newspapers
7228:Star-free
7182:Positive
7172:Decidable
7107:Positive
7031:Languages
6905:0302-9743
6864:0097-5397
6829:0004-5411
6711:: 25โ36.
6425:universal
6405:∀
6378:∃
6349:∅
6341:∀
6333:∩
6328:∃
6301:∀
6293:∪
6288:∃
6160:⟶
6152:ϵ
6146:ϵ
6135:−
6111:δ
6102:⋮
6086:−
6051:⟶
6043:ϵ
6037:ϵ
6008:δ
5963:⟶
5955:ϵ
5949:ϵ
5926:δ
5915:ϵ
5894:⟶
5873:ϵ
5862:−
5844:δ
5835:⋮
5824:ϵ
5803:⟶
5782:ϵ
5759:δ
5748:ϵ
5727:⟶
5683:δ
5649:≥
5638:∗
5634:Γ
5630:∈
5614:…
5579:≥
5568:∗
5564:Γ
5560:∈
5544:…
5510:ϵ
5506:Σ
5502:∈
5490:∈
5386:⟶
5370:⋅
5325:δ
5219:∗
5215:Γ
5211:×
5199:⟶
5194:∗
5190:Γ
5186:×
5181:ϵ
5177:Σ
5173:×
5150:δ
5088:Γ
5081:Σ
5024:δ
5015:Γ
5006:Σ
4678:ε
4625:α
4622:→
4596:α
4578:ε
4495:⊢
4471:⊢
4444:⊢
4414:⊢
4384:⊢
4357:⊢
4289:⊢
4262:⊢
4197:⊢
4173:⊢
4113:ϵ
4101:⊢
4089:ϵ
4077:⊢
4050:⊢
4020:⊢
3990:⊢
3963:⊢
3895:⊢
3868:⊢
3803:⊢
3779:⊢
3743:to state
3722:⊢
3679:α
3651:α
3625:to state
3606:α
3534:to state
3454:ϵ
3420:ϵ
3350:ϵ
3298:ϵ
3156:δ
3034:Γ
2992:Σ
2881:δ
2872:Γ
2863:Σ
2815:≥
2809:∣
2753:≥
2747:∣
2493:⊢
2478:reflexive
2462:∗
2453:⊢
2422:∈
2396:ε
2390:ε
2376:∗
2367:⊢
2328:∗
2324:Σ
2320:∈
2272:∗
2268:Γ
2264:∈
2261:γ
2238:∈
2212:γ
2206:ε
2192:∗
2183:⊢
2144:∗
2140:Σ
2136:∈
2089:ε
1930:β
1890:∗
1886:Γ
1882:∈
1879:γ
1857:∗
1853:Σ
1849:∈
1823:γ
1820:α
1796:⊢
1789:γ
1748:δ
1745:∈
1739:α
1666:⊢
1645:δ
1603:∗
1599:Γ
1595:×
1590:∗
1586:Σ
1582:×
1576:∈
1570:β
1513:δ
1510:∈
1412:δ
1409:∈
1361:∈
1275:δ
1174:δ
1149:∗
1145:Γ
1141:×
1118:Γ
1115:×
1106:ε
1100:∪
1097:Σ
1091:×
1064:δ
1032:ε
1026:∪
1023:Σ
998:∗
994:Γ
990:∈
987:α
907:Γ
904:∈
893:and with
878:ε
872:∪
869:Σ
866:∈
840:∈
777:δ
774:∈
768:α
711:⊆
683:Γ
680:∈
649:∈
612:∗
608:Γ
604:×
598:×
595:Γ
592:×
583:ε
577:∪
574:Σ
568:×
545:δ
520:Γ
495:Σ
419:δ
413:Γ
407:Σ
363:ε
343:Γ
317:∗
313:Γ
178:automaton
7026:Grammars
6919:(1997).
6485:See also
6114:′
6011:′
5929:′
5847:′
5762:′
5686:′
4751:Theorem.
2930:, where
2778:PDA for
2693:′
2647:′
2599:′
2553:′
2519:Theorem.
1448:because
215:design.
7249:Decider
7223:Regular
7190:Indexed
7148:Regular
7115:Indexed
6544:โ ฮต | 0
6539:grammar
6464:EXPTIME
6440:Chandra
5275:'s and
5136:
5116:
2935:states:
2712:Example
1076:is the
695:is the
664:is the
333:strings
282:general
160:In the
94:scholar
7301:Finite
7233:Finite
7078:Type-3
7069:Type-2
7051:Type-1
7045:Type-0
6931:
6903:
6893:
6862:
6827:
6774:J. ACM
6741:J. ACM
6646:
6456:Lipton
6452:Ladner
6423:resp.
6315:where
6243:DSPACE
6229:NSPACE
5459:where
5114:, and
5067:where
5046:
5030:
5021:
5012:
5003:
4639:expand
4549:expand
4542:Every
3663:(read
2912:
2903:
2887:
2878:
2869:
2860:
1527:finite
1012:. The
959:, pop
626:, the
484:states
459:where
278:(DPDA)
213:parser
96:
89:
82:
75:
67:
7259:PTIME
6957:JFLAP
6709:11558
6548:0 | 1
6517:Notes
6444:Kozen
6250:โ
log(
4949:. A
4715:match
4553:match
4345:00111
4250:00111
4209:00111
4185:00111
4161:00111
3435:, and
2444:Here
2411:with
2227:with
1227:with
1166:Here
284:, or
220:stack
197:below
195:(see
182:stack
101:JSTOR
87:books
7006:and
6963:CoAn
6929:ISBN
6901:ISSN
6891:ISBN
6860:ISSN
6825:ISSN
6644:ISBN
6458:and
6446:and
6392:and
6254:)).
5317:Let
4369:0111
4301:0111
4274:0111
3951:0011
3856:0011
3815:0011
3791:0011
3767:0011
3705:0011
2480:and
2253:and
355:and
168:, a
73:news
6883:doi
6852:doi
6815:doi
6782:doi
6749:doi
6713:doi
6604:doi
6433:all
6262:An
4426:111
4396:111
3975:011
3907:011
3880:011
3691:).
3671:by
3527:).
3515:by
1684:of
290:PDA
199:).
174:PDA
56:by
7349::
7002::
6899:.
6889:.
6858:.
6848:13
6846:.
6823:.
6811:28
6809:.
6805:.
6778:14
6776:.
6772:.
6745:14
6743:.
6739:.
6707:.
6666:.
6618:^
6598:.
6594:.
6580:^
6552:1.
6454:,
6450:.
6442:,
5664:.
5162::
4740:โ
4456:11
4032:11
4002:11
3568:.
3538:.
3517:AA
1904:.
379:.
296:.
288:,
246:A
184:.
7194:โ
7152:โ
7119:โ
7084:โ
7081:โ
7075:โ
7072:โ
7066:โ
7063:โ
7060:โ
7057:โ
7054:โ
7048:โ
6992:e
6985:t
6978:v
6937:.
6907:.
6885::
6866:.
6854::
6831:.
6817::
6790:.
6784::
6757:.
6751::
6719:.
6715::
6676:.
6652:.
6612:.
6606::
6600:1
6550:S
6546:S
6542:S
6401:Q
6374:Q
6361:.
6346:=
6337:Q
6324:Q
6297:Q
6284:Q
6280:=
6277:Q
6252:n
6248:n
6246:(
6234:n
6232:(
6194:.
6191:)
6186:1
6182:y
6178:,
6173:2
6169:q
6165:(
6155:)
6149:,
6143:,
6138:1
6132:n
6129:+
6126:m
6122:p
6118:(
6094:)
6089:1
6083:n
6079:y
6075:,
6070:2
6067:+
6064:m
6060:p
6056:(
6046:)
6040:,
6034:,
6029:1
6026:+
6023:m
6019:p
6015:(
6000:)
5995:n
5991:y
5987:,
5982:1
5979:+
5976:m
5972:p
5968:(
5958:)
5952:,
5946:,
5941:m
5937:p
5933:(
5918:)
5912:,
5907:m
5903:p
5899:(
5889:)
5884:m
5880:x
5876:,
5870:,
5865:1
5859:m
5855:p
5851:(
5827:)
5821:,
5816:2
5812:p
5808:(
5798:)
5793:2
5789:x
5785:,
5779:,
5774:1
5770:p
5766:(
5751:)
5745:,
5740:1
5736:p
5732:(
5722:)
5717:1
5713:x
5709:,
5706:w
5703:,
5698:1
5694:q
5690:(
5652:0
5646:n
5643:,
5625:n
5621:y
5617:,
5611:,
5606:2
5602:y
5598:,
5593:1
5589:y
5585:,
5582:0
5576:m
5573:,
5555:m
5551:x
5547:,
5541:,
5536:2
5532:x
5528:,
5523:1
5519:x
5515:,
5499:w
5496:,
5493:Q
5485:2
5481:q
5477:,
5472:1
5468:q
5444:)
5439:n
5435:y
5431:.
5428:.
5425:.
5420:2
5416:y
5410:1
5406:y
5402:,
5397:2
5393:q
5389:(
5383:)
5378:m
5374:x
5365:2
5361:x
5355:1
5351:x
5347:,
5344:w
5341:,
5336:1
5332:q
5328:(
5294:1
5291:+
5288:i
5284:b
5261:1
5258:+
5255:i
5251:a
5224:)
5208:Q
5205:(
5202:P
5170:Q
5124:F
5100:0
5096:q
5092:,
5085:,
5078:,
5075:Q
5052:)
5049:F
5043:,
5038:0
5034:q
5027:,
5018:,
5009:,
5000:,
4997:Q
4994:(
4991:=
4988:M
4930:)
4927:n
4924:(
4921:f
4901:n
4881:n
4861:f
4838:.
4826:)
4823:G
4820:(
4817:L
4814:=
4811:)
4808:M
4805:(
4802:N
4781:G
4761:M
4742:a
4738:A
4734:A
4732:,
4730:a
4717:)
4713:(
4701:a
4681:)
4675:,
4672:1
4669:,
4666:a
4663:,
4660:a
4657:,
4654:1
4651:(
4641:)
4637:(
4619:A
4599:)
4593:,
4590:1
4587:,
4584:A
4581:,
4575:,
4572:1
4569:(
4547:(
4516:)
4513:Z
4510:,
4507:1
4504:,
4501:r
4498:(
4492:)
4489:Z
4486:,
4483:1
4480:,
4477:q
4474:(
4468:)
4465:Z
4462:A
4459:,
4453:,
4450:q
4447:(
4441:)
4438:Z
4435:A
4432:A
4429:,
4423:,
4420:q
4417:(
4411:)
4408:Z
4405:A
4402:A
4399:,
4393:,
4390:p
4387:(
4381:)
4378:Z
4375:A
4372:,
4366:,
4363:p
4360:(
4354:)
4351:Z
4348:,
4342:,
4339:p
4336:(
4313:)
4310:Z
4307:A
4304:,
4298:,
4295:q
4292:(
4286:)
4283:Z
4280:A
4277:,
4271:,
4268:p
4265:(
4259:)
4256:Z
4253:,
4247:,
4244:p
4241:(
4218:)
4215:Z
4212:,
4206:,
4203:r
4200:(
4194:)
4191:Z
4188:,
4182:,
4179:q
4176:(
4170:)
4167:Z
4164:,
4158:,
4155:p
4152:(
4122:)
4119:Z
4116:,
4110:,
4107:r
4104:(
4098:)
4095:Z
4092:,
4086:,
4083:q
4080:(
4074:)
4071:Z
4068:A
4065:,
4062:1
4059:,
4056:q
4053:(
4047:)
4044:Z
4041:A
4038:A
4035:,
4029:,
4026:q
4023:(
4017:)
4014:Z
4011:A
4008:A
4005:,
3999:,
3996:p
3993:(
3987:)
3984:Z
3981:A
3978:,
3972:,
3969:p
3966:(
3960:)
3957:Z
3954:,
3948:,
3945:p
3942:(
3919:)
3916:Z
3913:A
3910:,
3904:,
3901:q
3898:(
3892:)
3889:Z
3886:A
3883:,
3877:,
3874:p
3871:(
3865:)
3862:Z
3859:,
3853:,
3850:p
3847:(
3824:)
3821:Z
3818:,
3812:,
3809:r
3806:(
3800:)
3797:Z
3794:,
3788:,
3785:q
3782:(
3776:)
3773:Z
3770:,
3764:,
3761:p
3758:(
3745:q
3741:p
3712:M
3669:A
3665:a
3647:/
3643:A
3640:;
3637:a
3627:q
3623:p
3609:)
3603:,
3600:q
3597:,
3594:A
3591:,
3588:a
3585:,
3582:p
3579:(
3566:Z
3562:r
3558:q
3551:A
3547:1
3543:q
3536:q
3532:p
3525:Z
3521:A
3513:A
3509:A
3505:A
3501:A
3497:0
3493:p
3487:.
3475:)
3472:Z
3469:,
3466:r
3463:,
3460:Z
3457:,
3451:,
3448:q
3445:(
3423:)
3417:,
3414:q
3411:,
3408:A
3405:,
3402:1
3399:,
3396:q
3393:(
3383:,
3371:)
3368:A
3365:,
3362:q
3359:,
3356:A
3353:,
3347:,
3344:p
3341:(
3331:,
3319:)
3316:Z
3313:,
3310:q
3307:,
3304:Z
3301:,
3295:,
3292:p
3289:(
3279:,
3267:)
3264:A
3261:A
3258:,
3255:p
3252:,
3249:A
3246:,
3243:0
3240:,
3237:p
3234:(
3224:,
3212:)
3209:Z
3206:A
3203:,
3200:p
3197:,
3194:Z
3191:,
3188:0
3185:,
3182:p
3179:(
3133:}
3130:r
3127:{
3124:=
3121:F
3107:Z
3089:p
3086:=
3081:0
3077:q
3052:}
3049:Z
3046:,
3043:A
3040:{
3037:=
3010:}
3007:1
3004:,
3001:0
2998:{
2995:=
2968:}
2965:r
2962:,
2959:q
2956:,
2953:p
2950:{
2947:=
2944:Q
2918:)
2915:F
2909:,
2906:Z
2900:,
2895:0
2891:q
2884:,
2875:,
2866:,
2857:,
2854:Q
2851:(
2848:=
2845:M
2821:}
2818:0
2812:n
2804:n
2800:1
2794:n
2790:0
2786:{
2759:}
2756:0
2750:n
2742:n
2738:1
2732:n
2728:0
2724:{
2697:)
2690:M
2686:(
2683:L
2680:=
2677:)
2674:M
2671:(
2668:N
2644:M
2623:M
2603:)
2596:M
2592:(
2589:N
2586:=
2583:)
2580:M
2577:(
2574:L
2550:M
2529:M
2497:M
2457:M
2428:}
2425:Q
2419:q
2399:)
2393:,
2387:,
2384:q
2381:(
2371:M
2363:)
2360:Z
2357:,
2354:w
2351:,
2346:0
2342:q
2338:(
2334:|
2317:w
2314:{
2311:=
2308:)
2305:M
2302:(
2299:N
2277:}
2241:F
2235:f
2215:)
2209:,
2203:,
2200:f
2197:(
2187:M
2179:)
2176:Z
2173:,
2170:w
2167:,
2162:0
2158:q
2154:(
2150:|
2133:w
2130:{
2127:=
2124:)
2121:M
2118:(
2115:L
2069:F
2049:)
2046:Z
2043:,
2040:w
2037:,
2032:0
2028:q
2024:(
2004:w
1984:Z
1962:0
1958:q
1933:)
1927:,
1924:w
1921:,
1918:p
1915:(
1846:x
1826:)
1817:,
1814:x
1811:,
1808:q
1805:(
1800:M
1792:)
1786:A
1783:,
1780:x
1777:a
1774:,
1771:p
1768:(
1742:)
1736:,
1733:q
1730:,
1727:A
1724:,
1721:a
1718:,
1715:p
1712:(
1692:M
1670:M
1625:M
1579:Q
1573:)
1567:,
1564:w
1561:,
1558:p
1555:(
1507:)
1504:}
1501:)
1498:A
1495:B
1492:,
1489:q
1486:(
1483:{
1480:,
1477:)
1474:A
1471:,
1468:a
1465:,
1462:p
1459:(
1456:(
1436:,
1433:)
1430:A
1427:,
1424:a
1421:,
1418:p
1415:(
1406:)
1403:A
1400:B
1397:,
1394:q
1391:(
1388:,
1385:}
1382:)
1379:A
1376:B
1373:,
1370:q
1367:(
1364:{
1358:)
1355:A
1352:B
1349:,
1346:q
1343:(
1323:}
1320:)
1317:A
1314:B
1311:,
1308:q
1305:(
1302:{
1299:=
1296:)
1293:A
1290:,
1287:a
1284:,
1281:p
1278:(
1255:a
1235:A
1215:p
1195:)
1192:A
1189:,
1186:a
1183:,
1180:p
1177:(
1138:Q
1112:)
1109:}
1103:{
1094:(
1088:Q
1038:)
1035:}
1029:{
1020:(
967:A
947:q
927:a
901:A
881:}
875:{
863:a
843:Q
837:p
817:M
797:M
771:)
765:,
762:q
759:,
756:A
753:,
750:a
747:,
744:p
741:(
714:Q
708:F
677:Z
652:Q
644:0
640:q
601:Q
589:)
586:}
580:{
571:(
565:Q
470:Q
447:)
444:F
441:,
438:Z
435:,
430:0
426:q
422:,
416:,
410:,
404:,
401:Q
398:(
395:=
392:M
172:(
123:)
117:(
112:)
108:(
98:ยท
91:ยท
84:ยท
77:ยท
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
