2933:
20:
2509:
1555:
3910:
1268:
3623:
3602:
While the pumping lemma states that all regular languages satisfy the conditions described above, the converse of this statement is not true: a language that satisfies these conditions may still be non-regular. In other words, both the original and the general version of the pumping lemma give a
51:—that is, have a middle section of the string repeated an arbitrary number of times—to produce a new string that is also part of the language. The pumping lemma is useful for proving that a specific language is not a regular language, by showing that that the language does not have the property.
1550:{\displaystyle {\begin{array}{l}\forall L\subseteq \Sigma ^{*},{\mbox{regular}}(L)\implies \\\quad \exists p\geq 1,\forall w\in L,|w|\geq p\implies \\\qquad \exists x,y,z\in \Sigma ^{*},(w=xyz)\land (|y|\geq 1)\land (|xy|\leq p)\land (\forall n\geq 0,xy^{n}z\in L)\end{array}}}
3905:{\displaystyle {\begin{matrix}L&=&\{uvwxy:u,y\in \{0,1,2,3\}^{*};v,w,x\in \{0,1,2,3\}\land (v=w\lor v=x\lor x=w)\}\\&&\cup \ \{w:w\in \{0,1,2,3\}^{*}\land {\text{precisely }}{\tfrac {1}{7}}{\text{ of the characters in }}w{\text{ are 3's}}\}\end{matrix}}}
3980:
with a substring of length 3 including a duplicate character, as well as all strings over this alphabet where precisely 1/7 of the string's characters are 3's. This language is not regular but can still be "pumped" with
4018:
If the duplicate characters are separated by 2 or 3 characters, pump 2 of the characters separating them. Pumping either down or up results in the creation of a substring of size 3 that contains 2 duplicate
4011:
has length at least 5. Then, since the alphabet has only four characters, at least two of the first five characters in the string must be duplicates. They are separated by at most three characters.
4481:
912:
4558:
1631:
23:
For every long enough string in a regular language, there must be a middle section (y) that can be repeated (or pumped) any number of times to produce a string still in the language.
346:
4015:
If the duplicate characters are separated by 0 characters, or 1, pump one of the other two characters in the string, which will not affect the substring containing the duplicates.
4112:
2716:
1669:
1844:
3978:
2561:
3417:
2095:
1938:
848:
3495:
3453:
3315:
3268:
2174:
1974:
808:
3541:
3186:
2366:
2250:
2053:
2007:
1711:
1238:
1212:
617:
3033:
3006:
2975:
2863:
2836:
2809:
2664:
1899:
1179:
749:
245:
4161:
4005:
3212:
2942:. Since this string has a length at least as large as the number of states, which is four (so the total number of states that the machine passes through to scan
2782:
1024:
409:
4181:
4132:
4060:
4040:
3934:
3589:
3569:
3515:
3378:
3358:
3338:
3232:
3160:
3117:
3093:
3069:
2923:
2903:
2883:
2756:
2736:
2637:
2617:
2581:
2498:
2478:
2458:
2438:
2409:
2386:
2330:
2310:
2290:
2270:
2217:
2194:
2135:
2115:
2027:
1864:
1801:
1781:
1758:
1731:
1258:
1147:
1127:
1107:
1084:
1064:
1044:
994:
974:
954:
934:
769:
717:
697:
677:
657:
637:
591:
536:
516:
496:
476:
449:
429:
386:
366:
266:
212:
192:
172:
152:
132:
112:
92:
72:
4878:
4551:
4441:
4222:
4217:
562:
4195:
provides a test that exactly characterizes regular languages. The typical method for proving that a language is regular is to construct either a
4765:
4544:
4527:
4491:
4455:
4419:
4391:
4352:
3594:
Since the general version imposes stricter requirements on the language, it can be used to prove the non-regularity of many more languages.
4690:
4780:
2950:
indicates that there must be at least one repeated state among the start state and the next four visited states. In this example, only
4705:
3604:
3127:
1568:
may consist of exhibiting a string (of the required length) in the language that lacks the property outlined in the pumping lemma.
4873:
4858:
4249:
2500:, a string can be produced that does not contain the same number of left and right parentheses, and so they cannot be balanced.
4734:
2599:(FSA) that accepts the language. The number of states in such an FSA are counted and that count is used as the pumping length
4344:
4282:
976:
to be pumped must be of length at least one, that is, not an empty string; (2) means the loop must occur within the first
4751:
4676:
4848:
854:
936:
is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in
4744:
19:
4192:
4184:
4920:
4669:
2513:
44:
2932:
4930:
4821:
4816:
1575:
4902:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
271:
4832:
4770:
4695:
2596:
1565:
4065:
4775:
4723:
4536:
4276:
4868:
4843:
4700:
4661:
4196:
2947:
2669:
1636:
388:
zero or more times is known as "pumping". Moreover, the pumping lemma guarantees that the length of
4297:
550:
36:
1806:
4853:
4795:
4739:
4200:
3939:
2526:
3383:
2061:
1904:
814:
4383:
4377:
3461:
3422:
3276:
3237:
2143:
1943:
777:
4588:
4523:
4487:
4451:
4415:
4387:
4348:
4447:
3520:
3165:
2338:
2222:
2032:
1979:
1678:
1217:
1184:
596:
4837:
4790:
4757:
4603:
4497:
4461:
4425:
4358:
4264:
4241:
4212:
3126:
As a side remark, the problem of checking whether a given string can be accepted by a given
2520:
542:
40:
3011:
2984:
2953:
2841:
2814:
2811:
for such a state. The transitions that take the machine from the first encounter of state
2787:
2642:
1872:
1152:
722:
218:
4925:
4800:
4715:
4682:
4598:
4571:
4567:
4501:
4465:
4429:
4362:
4137:
554:
28:
3984:
3191:
2761:
999:
391:
4811:
4593:
4575:
4477:
4437:
4166:
4117:
4045:
4025:
3919:
3574:
3554:
3500:
3363:
3343:
3323:
3217:
3145:
3102:
3078:
3054:
2908:
2888:
2868:
2741:
2721:
2622:
2602:
2566:
2483:
2463:
2443:
2423:
2394:
2371:
2315:
2295:
2275:
2255:
2202:
2179:
2120:
2100:
2012:
1849:
1786:
1766:
1743:
1716:
1243:
1132:
1112:
1092:
1069:
1049:
1029:
979:
959:
939:
919:
754:
702:
682:
662:
642:
622:
576:
521:
501:
481:
461:
434:
414:
371:
351:
251:
197:
177:
157:
137:
117:
97:
77:
57:
2508:
1564:
The pumping lemma is often used to prove that a particular language is non-regular: a
4914:
4896:
4473:
2417:
455:
3035:, that portion could be repeated and the FSA would still accept, giving the string
4517:
4863:
4785:
4710:
4513:
4339:
Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009).
4301:
4245:
558:
546:
1046:(conclusion of (1) and (2)), but apart from that, there is no restriction on
771:
can be divided into three substrings), satisfying the following conditions:
3043:
portion could be removed and the FSA would still accept giving the string
2925:
repeated any number of times, the conditions of the lemma are satisfied.
2784:
visited states there must be at least one state that is repeated. Write
1273:
4306:
Zeitschrift fĂĽr
Phonetik, Sprachwissenschaft und Kommunikationsforschung
4268:
3131:
2440:, there is a string of balanced parentheses that begins with more than
4304:(1961), "On formal properties of simple phrase structure grammars",
2885:
in the lemma, and since the machine will match a string without the
2738:
states visited as the string is emitted. Because the FSA has only
54:
Specifically, the pumping lemma says that for any regular language
4826:
4341:
Combinatorics on words. Christoffel words and repetitions in words
18:
4540:
4895:
Each category of languages, except those marked by a , is a
4323:
John E. Hopcroft; Rajeev
Motwani; Jeffrey D. Ullman (2003).
2563:) twice. Hence, after repeating ("pumping") the middle part
4483:
Introduction to
Automata Theory, Languages, and Computation
4325:
Introduction to
Automata Theory, Languages, and Computation
2981:
takes the machine through transitions that start at state
2480:
will consist entirely of left parentheses. By repeating
2418:
language of balanced (i.e., properly nested) parentheses
1869:
By the pumping lemma, there must exist a decomposition
4343:. CRM Monograph Series. Vol. 27. Providence, RI:
3871:
3628:
3138:
General version of pumping lemma for regular languages
1299:
4486:. Reading, Massachusetts: Addison-Wesley Publishing.
4169:
4140:
4120:
4068:
4048:
4028:
3987:
3942:
3922:
3626:
3577:
3557:
3523:
3503:
3464:
3425:
3386:
3366:
3346:
3326:
3279:
3240:
3220:
3194:
3168:
3148:
3105:
3081:
3057:
3014:
2987:
2956:
2911:
2891:
2871:
2844:
2817:
2790:
2764:
2744:
2724:
2672:
2645:
2625:
2605:
2569:
2529:
2486:
2466:
2446:
2426:
2397:
2374:
2341:
2318:
2298:
2278:
2258:
2225:
2205:
2182:
2146:
2123:
2103:
2064:
2035:
2015:
1982:
1946:
1907:
1875:
1852:
1809:
1789:
1769:
1746:
1719:
1681:
1639:
1578:
1271:
1246:
1220:
1187:
1155:
1135:
1115:
1095:
1072:
1052:
1032:
1002:
982:
962:
942:
922:
857:
817:
780:
757:
725:
705:
685:
665:
645:
625:
599:
579:
524:
504:
484:
464:
437:
417:
394:
374:
354:
274:
254:
221:
200:
180:
160:
140:
120:
100:
80:
60:
593:
be a regular language. Then there exists an integer
16:
A lemma that defines a property of regular languages
3551:standard version follows a special case, with both
1263:Below is a formal expression of the pumping lemma.
4271:. Archived from the original on December 14, 2010.
4175:
4155:
4126:
4106:
4054:
4034:
3999:
3972:
3928:
3904:
3583:
3563:
3535:
3509:
3489:
3447:
3411:
3372:
3352:
3332:
3309:
3262:
3226:
3206:
3180:
3154:
3111:
3087:
3063:
3027:
3000:
2969:
2917:
2897:
2877:
2857:
2830:
2803:
2776:
2750:
2730:
2710:
2658:
2631:
2611:
2575:
2555:
2492:
2472:
2452:
2432:
2403:
2380:
2360:
2324:
2304:
2284:
2264:
2244:
2211:
2188:
2176:, it contains at least one instance of the letter
2168:
2129:
2109:
2089:
2047:
2021:
2001:
1968:
1932:
1893:
1858:
1838:
1795:
1775:
1752:
1725:
1705:
1663:
1625:
1549:
1252:
1232:
1206:
1173:
1141:
1121:
1101:
1078:
1058:
1038:
1018:
988:
968:
948:
928:
906:
842:
802:
763:
743:
719:is called the "pumping length") can be written as
711:
691:
671:
651:
631:
611:
585:
530:
510:
490:
470:
443:
423:
403:
380:
360:
340:
260:
239:
206:
186:
166:
146:
126:
106:
86:
66:
43:. Informally, it says that all sufficiently long
2928:For example, the following image shows an FSA.
2252:gives a word with more instances of the letter
907:{\displaystyle (\forall n\geq 0)(xy^{n}z\in L)}
3617:For example, consider the following language:
4552:
4250:"Finite Automata and Their Decision Problems"
3047:. In terms of the pumping lemma, the string
2420:is not regular follows the same idea. Given
8:
3967:
3943:
3895:
3853:
3828:
3813:
3798:
3753:
3729:
3699:
3674:
3641:
3188:(the pumping length) such that every string
1658:
1646:
1620:
1585:
39:that describes an essential property of all
4874:Counter-free (with aperiodic finite monoid)
2591:, ...) the string will still be recognized.
1671:can be shown to be non-regular as follows:
549:in 1959, and rediscovered shortly after by
4584:
4559:
4545:
4537:
3130:without visiting any state repeatedly, is
2977:is a repeated state. Since the substring
2865:match some string. This string is called
1377:
1373:
1318:
1314:
1089:In simple words, for any regular language
454:Languages with a finite number of strings
4522:. Springer Science & Business Media.
4443:Introduction to the Theory of Computation
4168:
4139:
4119:
4098:
4079:
4067:
4047:
4027:
3986:
3941:
3921:
3890:
3882:
3870:
3865:
3856:
3702:
3627:
3625:
3576:
3556:
3522:
3502:
3475:
3463:
3434:
3426:
3424:
3398:
3387:
3385:
3365:
3345:
3325:
3278:
3249:
3241:
3239:
3219:
3193:
3167:
3147:
3104:
3080:
3056:
3019:
3013:
2992:
2986:
2961:
2955:
2910:
2890:
2870:
2849:
2843:
2822:
2816:
2795:
2789:
2763:
2743:
2723:
2702:
2677:
2671:
2650:
2644:
2624:
2604:
2568:
2547:
2534:
2528:
2512:Proof idea: Whenever a sufficiently long
2485:
2465:
2445:
2425:
2396:
2373:
2349:
2340:
2317:
2297:
2277:
2257:
2233:
2224:
2204:
2181:
2155:
2147:
2145:
2122:
2102:
2076:
2065:
2063:
2034:
2014:
1990:
1981:
1955:
1947:
1945:
1919:
1908:
1906:
1874:
1851:
1830:
1820:
1808:
1788:
1768:
1745:
1718:
1680:
1638:
1602:
1592:
1577:
1525:
1483:
1472:
1452:
1444:
1408:
1362:
1354:
1298:
1289:
1272:
1270:
1245:
1219:
1195:
1186:
1154:
1134:
1114:
1094:
1071:
1051:
1031:
1011:
1003:
1001:
981:
961:
941:
921:
886:
856:
829:
818:
816:
789:
781:
779:
756:
724:
704:
684:
664:
644:
624:
598:
578:
523:
503:
483:
463:
436:
416:
393:
373:
353:
273:
253:
220:
199:
179:
159:
139:
119:
99:
79:
59:
4223:Pumping lemma for regular tree languages
4218:Pumping lemma for context-free languages
2507:
1626:{\displaystyle L=\{a^{n}b^{n}:n\geq 0\}}
1560:Use of the lemma to prove non-regularity
563:pumping lemma for context-free languages
431:, imposing a limit on the ways in which
268:being non-empty), such that the strings
4257:IBM Journal of Research and Development
4233:
3936:contains all strings over the alphabet
3162:is regular, then there exists a number
498:plus one. By doing so, zero strings in
4766:Linear context-free rewriting language
4274:
2595:For every regular language there is a
1735:formal statement for the pumping lemma
561:in 1961, as a simplification of their
541:The pumping lemma was first proven by
478:equal to the maximum string length in
4691:Linear context-free rewriting systems
4440:(1997). "1.4: Nonregular Languages".
3548:
1734:
341:{\displaystyle xz,xyz,xyyz,xyyyz,...}
7:
4519:Automata Theory and its Applications
4062:is not regular: Consider the string
2388:which contradicts the pumping lemma.
458:satisfy the pumping lemma by having
4107:{\displaystyle (013)^{3m}(012)^{i}}
2523:, it must have reached some state (
154:can be split into three substrings
33:pumping lemma for regular languages
4899:of the category directly above it.
2619:. For a string of length at least
1640:
1503:
1405:
1383:
1339:
1324:
1286:
1276:
1149:) can be split into 3 parts. i.e.
861:
14:
3128:nondeterministic finite automaton
2838:to the second encounter of state
3884: of the characters in
3598:Invalidity of the lemma converse
2931:
2758:states, within this sequence of
1846:, which is a string longer than
1760:exists as required by the lemma.
2711:{\displaystyle q_{1},...,q_{p}}
1664:{\displaystyle \Sigma =\{a,b\}}
1382:
1323:
1109:, any sufficiently long string
4379:Abstract Machines and Grammars
4095:
4088:
4076:
4069:
3795:
3759:
3614:for a language to be regular.
3435:
3427:
3399:
3388:
3250:
3242:
2938:The FSA accepts the string:
2156:
2148:
2117:only consists of instances of
2077:
2066:
1956:
1948:
1920:
1909:
1540:
1500:
1494:
1484:
1473:
1469:
1463:
1453:
1445:
1441:
1435:
1417:
1374:
1363:
1355:
1315:
1311:
1305:
1012:
1004:
901:
876:
873:
858:
830:
819:
790:
782:
1:
4345:American Mathematical Society
47:in a regular language may be
3270:can be written in the form
2905:portion, or with the string
2718:be the sequence of the next
1839:{\displaystyle w=a^{p}b^{p}}
1181:, such that all the strings
4446:. PWS Publishing. pp.
3973:{\displaystyle \{0,1,2,3\}}
2666:be the start state and let
2556:{\displaystyle q_{s}=q_{t}}
2292:, since some instances of
368:. The process of repeating
4947:
4781:Deterministic context-free
4706:Deterministic context-free
3412:{\displaystyle |xy|\leq p}
2504:Proof of the pumping lemma
2460:left parentheses, so that
2090:{\displaystyle |xy|\leq p}
1933:{\displaystyle |xy|\leq p}
1740:Assume that some constant
843:{\displaystyle |xy|\leq p}
74:, there exists a constant
4892:
4854:Nondeterministic pushdown
4582:
4281:: CS1 maint: unfit URL (
3490:{\displaystyle uxy^{i}zv}
3448:{\displaystyle |y|\geq 1}
3310:{\displaystyle uwv=uxyzv}
3263:{\displaystyle |w|\geq p}
2169:{\displaystyle |y|\geq 1}
1969:{\displaystyle |y|\geq 1}
803:{\displaystyle |y|\geq 1}
518:have length greater than
4414:. Chapman and Hall/CRC.
4410:Lawson, Mark V. (2004).
4376:Savitch, Walter (1982).
4022:The second condition of
3591:being the empty string.
3536:{\displaystyle i\geq 0}
3181:{\displaystyle p\geq 1}
2361:{\displaystyle xy^{2}z}
2245:{\displaystyle xy^{2}z}
2048:{\displaystyle i\geq 0}
2002:{\displaystyle xy^{i}z}
1706:{\displaystyle w,x,y,z}
1233:{\displaystyle n\geq 0}
1207:{\displaystyle xy^{n}z}
639:such that every string
612:{\displaystyle p\geq 1}
4859:Deterministic pushdown
4735:Recursively enumerable
4512:Bakhadyr Khoussainov;
4183:is not regular by the
4177:
4157:
4128:
4108:
4056:
4036:
4007:. Suppose some string
4001:
3974:
3930:
3906:
3585:
3565:
3537:
3511:
3491:
3449:
3413:
3374:
3354:
3334:
3311:
3264:
3228:
3208:
3182:
3156:
3113:
3089:
3065:
3039:. Alternatively, the
3029:
3002:
2971:
2919:
2899:
2879:
2859:
2832:
2805:
2778:
2752:
2732:
2712:
2660:
2633:
2613:
2597:finite state automaton
2592:
2577:
2557:
2494:
2474:
2454:
2434:
2414:
2405:
2382:
2362:
2326:
2306:
2286:
2266:
2246:
2213:
2190:
2170:
2131:
2111:
2091:
2049:
2023:
2003:
1970:
1934:
1895:
1860:
1840:
1797:
1777:
1754:
1727:
1707:
1665:
1627:
1572:Example: The language
1566:proof by contradiction
1551:
1254:
1234:
1208:
1175:
1143:
1123:
1103:
1080:
1060:
1040:
1020:
990:
970:
956:). (1) means the loop
950:
930:
908:
844:
804:
765:
745:
713:
693:
673:
653:
633:
613:
587:
532:
512:
492:
472:
445:
425:
405:
382:
362:
342:
262:
241:
208:
188:
168:
148:
128:
108:
88:
68:
24:
4329:Here: Sect.4.6, p.166
4193:Myhill–Nerode theorem
4185:Myhill–Nerode theorem
4178:
4158:
4129:
4109:
4057:
4037:
4002:
3975:
3931:
3907:
3586:
3566:
3538:
3512:
3492:
3450:
3414:
3375:
3355:
3335:
3312:
3265:
3229:
3209:
3183:
3157:
3114:
3090:
3066:
3030:
3028:{\displaystyle q_{1}}
3003:
3001:{\displaystyle q_{1}}
2972:
2970:{\displaystyle q_{1}}
2920:
2900:
2880:
2860:
2858:{\displaystyle q_{s}}
2833:
2831:{\displaystyle q_{s}}
2806:
2804:{\displaystyle q_{s}}
2779:
2753:
2733:
2713:
2661:
2659:{\displaystyle q_{0}}
2634:
2614:
2578:
2558:
2511:
2495:
2475:
2455:
2435:
2406:
2383:
2363:
2327:
2307:
2287:
2267:
2247:
2214:
2191:
2171:
2132:
2112:
2092:
2050:
2024:
2004:
1971:
1935:
1896:
1894:{\displaystyle w=xyz}
1861:
1841:
1798:
1778:
1755:
1728:
1708:
1666:
1628:
1570:
1552:
1255:
1235:
1209:
1176:
1174:{\displaystyle w=xyz}
1144:
1124:
1104:
1081:
1061:
1041:
1026:must be smaller than
1021:
991:
971:
951:
931:
909:
845:
805:
766:
746:
744:{\displaystyle w=xyz}
714:
694:
674:
654:
634:
614:
588:
533:
513:
493:
473:
446:
426:
406:
383:
363:
343:
263:
242:
240:{\displaystyle w=xyz}
209:
189:
169:
149:
134:with length at least
129:
109:
94:such that any string
89:
69:
22:
4844:Tree stack automaton
4287:Here: Lemma 8, p.119
4197:finite state machine
4167:
4156:{\displaystyle i=4m}
4138:
4118:
4114:. This string is in
4066:
4046:
4026:
3985:
3940:
3920:
3624:
3575:
3555:
3521:
3501:
3462:
3423:
3384:
3364:
3344:
3324:
3277:
3238:
3218:
3192:
3166:
3146:
3103:
3079:
3055:
3012:
2985:
2954:
2948:pigeonhole principle
2909:
2889:
2869:
2842:
2815:
2788:
2762:
2742:
2722:
2670:
2643:
2623:
2603:
2567:
2527:
2484:
2464:
2444:
2424:
2395:
2372:
2339:
2316:
2296:
2276:
2256:
2223:
2203:
2180:
2144:
2121:
2101:
2062:
2033:
2013:
1980:
1944:
1905:
1873:
1850:
1807:
1787:
1767:
1744:
1717:
1679:
1637:
1576:
1269:
1244:
1218:
1185:
1153:
1133:
1113:
1093:
1070:
1050:
1030:
1000:
980:
960:
940:
920:
855:
815:
778:
755:
723:
703:
683:
663:
643:
623:
597:
577:
522:
502:
482:
462:
435:
415:
392:
372:
352:
272:
252:
219:
198:
178:
158:
138:
118:
98:
78:
58:
4752:range concatenation
4677:range concatenation
4516:(6 December 2012).
4000:{\displaystyle p=5}
3207:{\displaystyle uwv}
2777:{\displaystyle p+1}
2583:arbitrarily often (
2519:is recognized by a
2416:The proof that the
1019:{\displaystyle |x|}
679:of length at least
551:Yehoshua Bar-Hillel
4478:Ullman, Jeffrey D.
4269:10.1147/rd.32.0114
4203:for the language.
4201:regular expression
4173:
4153:
4124:
4104:
4052:
4032:
3997:
3970:
3926:
3902:
3900:
3880:
3581:
3561:
3533:
3517:for every integer
3507:
3487:
3445:
3409:
3370:
3350:
3330:
3307:
3260:
3224:
3204:
3178:
3152:
3109:
3085:
3061:
3051:is broken into an
3025:
2998:
2967:
2915:
2895:
2875:
2855:
2828:
2801:
2774:
2748:
2728:
2708:
2656:
2629:
2609:
2593:
2573:
2553:
2490:
2470:
2450:
2430:
2411:cannot be regular.
2401:
2378:
2358:
2322:
2302:
2282:
2262:
2242:
2209:
2186:
2166:
2127:
2107:
2087:
2045:
2019:
1999:
1966:
1930:
1891:
1856:
1836:
1793:
1773:
1750:
1733:be as used in the
1723:
1703:
1661:
1633:over the alphabet
1623:
1547:
1545:
1303:
1250:
1230:
1204:
1171:
1139:
1119:
1099:
1076:
1056:
1036:
1016:
986:
966:
946:
926:
904:
840:
800:
761:
741:
709:
689:
669:
649:
629:
619:depending only on
609:
583:
528:
508:
488:
468:
441:
421:
404:{\displaystyle xy}
401:
378:
358:
338:
258:
237:
204:
184:
164:
144:
124:
104:
84:
64:
25:
4908:
4907:
4887:
4886:
4849:Embedded pushdown
4745:Context-sensitive
4670:Context-sensitive
4604:Abstract machines
4589:Chomsky hierarchy
4529:978-1-4612-0171-7
4493:978-0-201-02988-8
4474:Hopcroft, John E.
4457:978-0-534-94728-6
4421:978-1-58488-255-8
4393:978-0-316-77161-0
4354:978-0-8218-4480-9
4327:. Addison Wesley.
4176:{\displaystyle L}
4127:{\displaystyle L}
4055:{\displaystyle L}
4035:{\displaystyle L}
3929:{\displaystyle L}
3893:
3885:
3879:
3868:
3812:
3584:{\displaystyle v}
3564:{\displaystyle u}
3510:{\displaystyle L}
3373:{\displaystyle z}
3353:{\displaystyle y}
3333:{\displaystyle x}
3227:{\displaystyle L}
3155:{\displaystyle L}
3112:{\displaystyle z}
3088:{\displaystyle y}
3064:{\displaystyle x}
3008:and end at state
2946:would be 5), the
2918:{\displaystyle y}
2898:{\displaystyle y}
2878:{\displaystyle y}
2751:{\displaystyle p}
2731:{\displaystyle p}
2632:{\displaystyle p}
2612:{\displaystyle p}
2576:{\displaystyle y}
2493:{\displaystyle y}
2473:{\displaystyle y}
2453:{\displaystyle p}
2433:{\displaystyle p}
2404:{\displaystyle L}
2381:{\displaystyle L}
2325:{\displaystyle b}
2305:{\displaystyle a}
2285:{\displaystyle b}
2265:{\displaystyle a}
2212:{\displaystyle y}
2189:{\displaystyle a}
2130:{\displaystyle a}
2110:{\displaystyle y}
2022:{\displaystyle L}
1859:{\displaystyle p}
1796:{\displaystyle L}
1776:{\displaystyle w}
1753:{\displaystyle p}
1726:{\displaystyle n}
1302:
1253:{\displaystyle L}
1142:{\displaystyle L}
1122:{\displaystyle w}
1102:{\displaystyle L}
1079:{\displaystyle z}
1059:{\displaystyle x}
1039:{\displaystyle p}
989:{\displaystyle p}
969:{\displaystyle y}
949:{\displaystyle L}
929:{\displaystyle y}
764:{\displaystyle w}
712:{\displaystyle p}
692:{\displaystyle p}
672:{\displaystyle L}
652:{\displaystyle w}
632:{\displaystyle L}
586:{\displaystyle L}
531:{\displaystyle p}
511:{\displaystyle L}
491:{\displaystyle L}
471:{\displaystyle p}
444:{\displaystyle w}
424:{\displaystyle p}
381:{\displaystyle y}
361:{\displaystyle L}
261:{\displaystyle y}
207:{\displaystyle z}
187:{\displaystyle y}
167:{\displaystyle x}
147:{\displaystyle p}
127:{\displaystyle L}
107:{\displaystyle w}
87:{\displaystyle p}
67:{\displaystyle L}
41:regular languages
27:In the theory of
4938:
4921:Formal languages
4903:
4900:
4864:Visibly pushdown
4838:Thread automaton
4786:Visibly pushdown
4754:
4711:Visibly pushdown
4679:
4666:(no common name)
4585:
4572:formal languages
4561:
4554:
4547:
4538:
4533:
4507:(See chapter 3.)
4505:
4469:
4433:
4398:
4397:
4373:
4367:
4366:
4336:
4330:
4328:
4320:
4314:
4313:
4294:
4288:
4286:
4280:
4272:
4254:
4238:
4182:
4180:
4179:
4174:
4162:
4160:
4159:
4154:
4133:
4131:
4130:
4125:
4113:
4111:
4110:
4105:
4103:
4102:
4087:
4086:
4061:
4059:
4058:
4053:
4041:
4039:
4038:
4033:
4006:
4004:
4003:
3998:
3979:
3977:
3976:
3971:
3935:
3933:
3932:
3927:
3916:In other words,
3911:
3909:
3908:
3903:
3901:
3894:
3891:
3886:
3883:
3881:
3872:
3869:
3866:
3861:
3860:
3810:
3805:
3804:
3707:
3706:
3590:
3588:
3587:
3582:
3570:
3568:
3567:
3562:
3542:
3540:
3539:
3534:
3516:
3514:
3513:
3508:
3496:
3494:
3493:
3488:
3480:
3479:
3454:
3452:
3451:
3446:
3438:
3430:
3418:
3416:
3415:
3410:
3402:
3391:
3379:
3377:
3376:
3371:
3359:
3357:
3356:
3351:
3339:
3337:
3336:
3331:
3316:
3314:
3313:
3308:
3269:
3267:
3266:
3261:
3253:
3245:
3233:
3231:
3230:
3225:
3213:
3211:
3210:
3205:
3187:
3185:
3184:
3179:
3161:
3159:
3158:
3153:
3118:
3116:
3115:
3110:
3094:
3092:
3091:
3086:
3070:
3068:
3067:
3062:
3034:
3032:
3031:
3026:
3024:
3023:
3007:
3005:
3004:
2999:
2997:
2996:
2976:
2974:
2973:
2968:
2966:
2965:
2935:
2924:
2922:
2921:
2916:
2904:
2902:
2901:
2896:
2884:
2882:
2881:
2876:
2864:
2862:
2861:
2856:
2854:
2853:
2837:
2835:
2834:
2829:
2827:
2826:
2810:
2808:
2807:
2802:
2800:
2799:
2783:
2781:
2780:
2775:
2757:
2755:
2754:
2749:
2737:
2735:
2734:
2729:
2717:
2715:
2714:
2709:
2707:
2706:
2682:
2681:
2665:
2663:
2662:
2657:
2655:
2654:
2638:
2636:
2635:
2630:
2618:
2616:
2615:
2610:
2582:
2580:
2579:
2574:
2562:
2560:
2559:
2554:
2552:
2551:
2539:
2538:
2521:finite automaton
2499:
2497:
2496:
2491:
2479:
2477:
2476:
2471:
2459:
2457:
2456:
2451:
2439:
2437:
2436:
2431:
2410:
2408:
2407:
2402:
2387:
2385:
2384:
2379:
2367:
2365:
2364:
2359:
2354:
2353:
2331:
2329:
2328:
2323:
2311:
2309:
2308:
2303:
2291:
2289:
2288:
2283:
2272:than the letter
2271:
2269:
2268:
2263:
2251:
2249:
2248:
2243:
2238:
2237:
2218:
2216:
2215:
2210:
2195:
2193:
2192:
2187:
2175:
2173:
2172:
2167:
2159:
2151:
2136:
2134:
2133:
2128:
2116:
2114:
2113:
2108:
2096:
2094:
2093:
2088:
2080:
2069:
2054:
2052:
2051:
2046:
2028:
2026:
2025:
2020:
2008:
2006:
2005:
2000:
1995:
1994:
1975:
1973:
1972:
1967:
1959:
1951:
1939:
1937:
1936:
1931:
1923:
1912:
1900:
1898:
1897:
1892:
1865:
1863:
1862:
1857:
1845:
1843:
1842:
1837:
1835:
1834:
1825:
1824:
1802:
1800:
1799:
1794:
1782:
1780:
1779:
1774:
1759:
1757:
1756:
1751:
1732:
1730:
1729:
1724:
1712:
1710:
1709:
1704:
1670:
1668:
1667:
1662:
1632:
1630:
1629:
1624:
1607:
1606:
1597:
1596:
1556:
1554:
1553:
1548:
1546:
1530:
1529:
1487:
1476:
1456:
1448:
1413:
1412:
1366:
1358:
1304:
1300:
1294:
1293:
1259:
1257:
1256:
1251:
1239:
1237:
1236:
1231:
1213:
1211:
1210:
1205:
1200:
1199:
1180:
1178:
1177:
1172:
1148:
1146:
1145:
1140:
1128:
1126:
1125:
1120:
1108:
1106:
1105:
1100:
1085:
1083:
1082:
1077:
1065:
1063:
1062:
1057:
1045:
1043:
1042:
1037:
1025:
1023:
1022:
1017:
1015:
1007:
995:
993:
992:
987:
975:
973:
972:
967:
955:
953:
952:
947:
935:
933:
932:
927:
913:
911:
910:
905:
891:
890:
849:
847:
846:
841:
833:
822:
809:
807:
806:
801:
793:
785:
770:
768:
767:
762:
750:
748:
747:
742:
718:
716:
715:
710:
698:
696:
695:
690:
678:
676:
675:
670:
658:
656:
655:
650:
638:
636:
635:
630:
618:
616:
615:
610:
592:
590:
589:
584:
569:Formal statement
537:
535:
534:
529:
517:
515:
514:
509:
497:
495:
494:
489:
477:
475:
474:
469:
450:
448:
447:
442:
430:
428:
427:
422:
411:will be at most
410:
408:
407:
402:
387:
385:
384:
379:
367:
365:
364:
359:
347:
345:
344:
339:
267:
265:
264:
259:
247:
246:
244:
243:
238:
213:
211:
210:
205:
193:
191:
190:
185:
173:
171:
170:
165:
153:
151:
150:
145:
133:
131:
130:
125:
113:
111:
110:
105:
93:
91:
90:
85:
73:
71:
70:
65:
29:formal languages
4946:
4945:
4941:
4940:
4939:
4937:
4936:
4935:
4931:Finite automata
4911:
4910:
4909:
4904:
4901:
4894:
4888:
4883:
4805:
4749:
4728:
4674:
4655:
4578:
4576:formal grammars
4568:Automata theory
4565:
4530:
4511:
4494:
4472:
4458:
4438:Sipser, Michael
4436:
4422:
4412:Finite automata
4409:
4406:
4401:
4394:
4375:
4374:
4370:
4355:
4338:
4337:
4333:
4322:
4321:
4317:
4296:
4295:
4291:
4273:
4252:
4240:
4239:
4235:
4231:
4209:
4165:
4164:
4136:
4135:
4116:
4115:
4094:
4075:
4064:
4063:
4044:
4043:
4024:
4023:
3983:
3982:
3938:
3937:
3918:
3917:
3899:
3898:
3867:precisely
3852:
3802:
3801:
3698:
3639:
3634:
3622:
3621:
3600:
3573:
3572:
3553:
3552:
3547:From this, the
3519:
3518:
3499:
3498:
3471:
3460:
3459:
3421:
3420:
3382:
3381:
3362:
3361:
3342:
3341:
3322:
3321:
3275:
3274:
3236:
3235:
3216:
3215:
3190:
3189:
3164:
3163:
3144:
3143:
3140:
3101:
3100:
3077:
3076:
3053:
3052:
3015:
3010:
3009:
2988:
2983:
2982:
2957:
2952:
2951:
2907:
2906:
2887:
2886:
2867:
2866:
2845:
2840:
2839:
2818:
2813:
2812:
2791:
2786:
2785:
2760:
2759:
2740:
2739:
2720:
2719:
2698:
2673:
2668:
2667:
2646:
2641:
2640:
2621:
2620:
2601:
2600:
2565:
2564:
2543:
2530:
2525:
2524:
2506:
2482:
2481:
2462:
2461:
2442:
2441:
2422:
2421:
2393:
2392:
2370:
2369:
2345:
2337:
2336:
2314:
2313:
2294:
2293:
2274:
2273:
2254:
2253:
2229:
2221:
2220:
2201:
2200:
2178:
2177:
2142:
2141:
2119:
2118:
2099:
2098:
2060:
2059:
2031:
2030:
2011:
2010:
1986:
1978:
1977:
1942:
1941:
1903:
1902:
1871:
1870:
1848:
1847:
1826:
1816:
1805:
1804:
1785:
1784:
1765:
1764:
1742:
1741:
1715:
1714:
1677:
1676:
1635:
1634:
1598:
1588:
1574:
1573:
1562:
1544:
1543:
1521:
1404:
1379:
1378:
1320:
1319:
1285:
1267:
1266:
1242:
1241:
1216:
1215:
1191:
1183:
1182:
1151:
1150:
1131:
1130:
1111:
1110:
1091:
1090:
1068:
1067:
1048:
1047:
1028:
1027:
998:
997:
978:
977:
958:
957:
938:
937:
918:
917:
882:
853:
852:
813:
812:
776:
775:
753:
752:
721:
720:
701:
700:
681:
680:
661:
660:
641:
640:
621:
620:
595:
594:
575:
574:
571:
555:Micha A. Perles
520:
519:
500:
499:
480:
479:
460:
459:
451:may be split.
433:
432:
413:
412:
390:
389:
370:
369:
350:
349:
270:
269:
250:
249:
217:
216:
215:
196:
195:
176:
175:
156:
155:
136:
135:
116:
115:
96:
95:
76:
75:
56:
55:
17:
12:
11:
5:
4944:
4942:
4934:
4933:
4928:
4923:
4913:
4912:
4906:
4905:
4893:
4890:
4889:
4885:
4884:
4882:
4881:
4879:Acyclic finite
4876:
4871:
4866:
4861:
4856:
4851:
4846:
4840:
4835:
4830:
4829:Turing Machine
4824:
4822:Linear-bounded
4819:
4814:
4812:Turing machine
4808:
4806:
4804:
4803:
4798:
4793:
4788:
4783:
4778:
4773:
4771:Tree-adjoining
4768:
4763:
4760:
4755:
4747:
4742:
4737:
4731:
4729:
4727:
4726:
4721:
4718:
4713:
4708:
4703:
4698:
4696:Tree-adjoining
4693:
4688:
4685:
4680:
4672:
4667:
4664:
4658:
4656:
4654:
4653:
4650:
4647:
4644:
4641:
4638:
4635:
4632:
4629:
4626:
4623:
4620:
4617:
4614:
4610:
4607:
4606:
4601:
4596:
4591:
4583:
4580:
4579:
4566:
4564:
4563:
4556:
4549:
4541:
4535:
4534:
4528:
4509:
4492:
4470:
4456:
4434:
4420:
4405:
4402:
4400:
4399:
4392:
4368:
4353:
4347:. p. 86.
4331:
4315:
4300:; Perles, M.;
4298:Bar-Hillel, Y.
4289:
4263:(2): 114–125.
4242:Rabin, Michael
4232:
4230:
4227:
4226:
4225:
4220:
4215:
4208:
4205:
4189:
4188:
4172:
4152:
4149:
4146:
4143:
4123:
4101:
4097:
4093:
4090:
4085:
4082:
4078:
4074:
4071:
4051:
4031:
4020:
4016:
3996:
3993:
3990:
3969:
3966:
3963:
3960:
3957:
3954:
3951:
3948:
3945:
3925:
3914:
3913:
3897:
3889:
3878:
3875:
3864:
3859:
3855:
3851:
3848:
3845:
3842:
3839:
3836:
3833:
3830:
3827:
3824:
3821:
3818:
3815:
3809:
3806:
3803:
3800:
3797:
3794:
3791:
3788:
3785:
3782:
3779:
3776:
3773:
3770:
3767:
3764:
3761:
3758:
3755:
3752:
3749:
3746:
3743:
3740:
3737:
3734:
3731:
3728:
3725:
3722:
3719:
3716:
3713:
3710:
3705:
3701:
3697:
3694:
3691:
3688:
3685:
3682:
3679:
3676:
3673:
3670:
3667:
3664:
3661:
3658:
3655:
3652:
3649:
3646:
3643:
3640:
3638:
3635:
3633:
3630:
3629:
3599:
3596:
3580:
3560:
3545:
3544:
3532:
3529:
3526:
3506:
3486:
3483:
3478:
3474:
3470:
3467:
3444:
3441:
3437:
3433:
3429:
3408:
3405:
3401:
3397:
3394:
3390:
3369:
3349:
3329:
3318:
3317:
3306:
3303:
3300:
3297:
3294:
3291:
3288:
3285:
3282:
3259:
3256:
3252:
3248:
3244:
3223:
3203:
3200:
3197:
3177:
3174:
3171:
3151:
3142:If a language
3139:
3136:
3108:
3084:
3060:
3022:
3018:
2995:
2991:
2964:
2960:
2914:
2894:
2874:
2852:
2848:
2825:
2821:
2798:
2794:
2773:
2770:
2767:
2747:
2727:
2705:
2701:
2697:
2694:
2691:
2688:
2685:
2680:
2676:
2653:
2649:
2628:
2608:
2572:
2550:
2546:
2542:
2537:
2533:
2505:
2502:
2489:
2469:
2449:
2429:
2413:
2412:
2400:
2389:
2377:
2357:
2352:
2348:
2344:
2333:
2321:
2301:
2281:
2261:
2241:
2236:
2232:
2228:
2208:
2197:
2185:
2165:
2162:
2158:
2154:
2150:
2138:
2126:
2106:
2086:
2083:
2079:
2075:
2072:
2068:
2056:
2044:
2041:
2038:
2018:
1998:
1993:
1989:
1985:
1965:
1962:
1958:
1954:
1950:
1929:
1926:
1922:
1918:
1915:
1911:
1890:
1887:
1884:
1881:
1878:
1867:
1855:
1833:
1829:
1823:
1819:
1815:
1812:
1792:
1772:
1761:
1749:
1738:
1722:
1702:
1699:
1696:
1693:
1690:
1687:
1684:
1660:
1657:
1654:
1651:
1648:
1645:
1642:
1622:
1619:
1616:
1613:
1610:
1605:
1601:
1595:
1591:
1587:
1584:
1581:
1561:
1558:
1542:
1539:
1536:
1533:
1528:
1524:
1520:
1517:
1514:
1511:
1508:
1505:
1502:
1499:
1496:
1493:
1490:
1486:
1482:
1479:
1475:
1471:
1468:
1465:
1462:
1459:
1455:
1451:
1447:
1443:
1440:
1437:
1434:
1431:
1428:
1425:
1422:
1419:
1416:
1411:
1407:
1403:
1400:
1397:
1394:
1391:
1388:
1385:
1381:
1380:
1376:
1372:
1369:
1365:
1361:
1357:
1353:
1350:
1347:
1344:
1341:
1338:
1335:
1332:
1329:
1326:
1322:
1321:
1317:
1313:
1310:
1307:
1297:
1292:
1288:
1284:
1281:
1278:
1275:
1274:
1249:
1229:
1226:
1223:
1203:
1198:
1194:
1190:
1170:
1167:
1164:
1161:
1158:
1138:
1118:
1098:
1075:
1055:
1035:
1014:
1010:
1006:
985:
965:
945:
925:
915:
914:
903:
900:
897:
894:
889:
885:
881:
878:
875:
872:
869:
866:
863:
860:
850:
839:
836:
832:
828:
825:
821:
810:
799:
796:
792:
788:
784:
760:
740:
737:
734:
731:
728:
708:
688:
668:
648:
628:
608:
605:
602:
582:
570:
567:
527:
507:
487:
467:
440:
420:
400:
397:
377:
357:
337:
334:
331:
328:
325:
322:
319:
316:
313:
310:
307:
304:
301:
298:
295:
292:
289:
286:
283:
280:
277:
257:
236:
233:
230:
227:
224:
203:
183:
163:
143:
123:
103:
83:
63:
15:
13:
10:
9:
6:
4:
3:
2:
4943:
4932:
4929:
4927:
4924:
4922:
4919:
4918:
4916:
4898:
4897:proper subset
4891:
4880:
4877:
4875:
4872:
4870:
4867:
4865:
4862:
4860:
4857:
4855:
4852:
4850:
4847:
4845:
4841:
4839:
4836:
4834:
4831:
4828:
4825:
4823:
4820:
4818:
4815:
4813:
4810:
4809:
4807:
4802:
4799:
4797:
4794:
4792:
4789:
4787:
4784:
4782:
4779:
4777:
4774:
4772:
4769:
4767:
4764:
4761:
4759:
4756:
4753:
4748:
4746:
4743:
4741:
4738:
4736:
4733:
4732:
4730:
4725:
4724:Non-recursive
4722:
4719:
4717:
4714:
4712:
4709:
4707:
4704:
4702:
4699:
4697:
4694:
4692:
4689:
4686:
4684:
4681:
4678:
4673:
4671:
4668:
4665:
4663:
4660:
4659:
4657:
4651:
4648:
4645:
4642:
4639:
4636:
4633:
4630:
4627:
4624:
4621:
4618:
4615:
4612:
4611:
4609:
4608:
4605:
4602:
4600:
4597:
4595:
4592:
4590:
4587:
4586:
4581:
4577:
4573:
4569:
4562:
4557:
4555:
4550:
4548:
4543:
4542:
4539:
4531:
4525:
4521:
4520:
4515:
4510:
4508:
4503:
4499:
4495:
4489:
4485:
4484:
4479:
4475:
4471:
4467:
4463:
4459:
4453:
4449:
4445:
4444:
4439:
4435:
4431:
4427:
4423:
4417:
4413:
4408:
4407:
4403:
4395:
4389:
4385:
4381:
4380:
4372:
4369:
4364:
4360:
4356:
4350:
4346:
4342:
4335:
4332:
4326:
4319:
4316:
4311:
4307:
4303:
4299:
4293:
4290:
4284:
4278:
4270:
4266:
4262:
4258:
4251:
4247:
4243:
4237:
4234:
4228:
4224:
4221:
4219:
4216:
4214:
4213:Ogden's lemma
4211:
4210:
4206:
4204:
4202:
4198:
4194:
4186:
4170:
4150:
4147:
4144:
4141:
4134:exactly when
4121:
4099:
4091:
4083:
4080:
4072:
4049:
4042:ensures that
4029:
4021:
4017:
4014:
4013:
4012:
4010:
3994:
3991:
3988:
3964:
3961:
3958:
3955:
3952:
3949:
3946:
3923:
3892: are 3's
3887:
3876:
3873:
3862:
3857:
3849:
3846:
3843:
3840:
3837:
3834:
3831:
3825:
3822:
3819:
3816:
3807:
3792:
3789:
3786:
3783:
3780:
3777:
3774:
3771:
3768:
3765:
3762:
3756:
3750:
3747:
3744:
3741:
3738:
3735:
3732:
3726:
3723:
3720:
3717:
3714:
3711:
3708:
3703:
3695:
3692:
3689:
3686:
3683:
3680:
3677:
3671:
3668:
3665:
3662:
3659:
3656:
3653:
3650:
3647:
3644:
3636:
3631:
3620:
3619:
3618:
3615:
3613:
3611:
3607:
3597:
3595:
3592:
3578:
3558:
3550:
3530:
3527:
3524:
3504:
3484:
3481:
3476:
3472:
3468:
3465:
3458:
3457:
3456:
3442:
3439:
3431:
3406:
3403:
3395:
3392:
3367:
3347:
3327:
3320:with strings
3304:
3301:
3298:
3295:
3292:
3289:
3286:
3283:
3280:
3273:
3272:
3271:
3257:
3254:
3246:
3221:
3201:
3198:
3195:
3175:
3172:
3169:
3149:
3137:
3135:
3133:
3129:
3124:
3122:
3106:
3098:
3082:
3074:
3058:
3050:
3046:
3042:
3038:
3020:
3016:
2993:
2989:
2980:
2962:
2958:
2949:
2945:
2941:
2936:
2934:
2929:
2926:
2912:
2892:
2872:
2850:
2846:
2823:
2819:
2796:
2792:
2771:
2768:
2765:
2745:
2725:
2703:
2699:
2695:
2692:
2689:
2686:
2683:
2678:
2674:
2651:
2647:
2626:
2606:
2598:
2590:
2586:
2570:
2548:
2544:
2540:
2535:
2531:
2522:
2518:
2515:
2510:
2503:
2501:
2487:
2467:
2447:
2427:
2419:
2398:
2390:
2375:
2355:
2350:
2346:
2342:
2334:
2319:
2299:
2279:
2259:
2239:
2234:
2230:
2226:
2206:
2198:
2183:
2163:
2160:
2152:
2139:
2124:
2104:
2097:, the string
2084:
2081:
2073:
2070:
2057:
2042:
2039:
2036:
2016:
1996:
1991:
1987:
1983:
1963:
1960:
1952:
1927:
1924:
1916:
1913:
1888:
1885:
1882:
1879:
1876:
1868:
1853:
1831:
1827:
1821:
1817:
1813:
1810:
1790:
1770:
1762:
1747:
1739:
1736:
1720:
1700:
1697:
1694:
1691:
1688:
1685:
1682:
1674:
1673:
1672:
1655:
1652:
1649:
1643:
1617:
1614:
1611:
1608:
1603:
1599:
1593:
1589:
1582:
1579:
1569:
1567:
1559:
1557:
1537:
1534:
1531:
1526:
1522:
1518:
1515:
1512:
1509:
1506:
1497:
1491:
1488:
1480:
1477:
1466:
1460:
1457:
1449:
1438:
1432:
1429:
1426:
1423:
1420:
1414:
1409:
1401:
1398:
1395:
1392:
1389:
1386:
1370:
1367:
1359:
1351:
1348:
1345:
1342:
1336:
1333:
1330:
1327:
1308:
1295:
1290:
1282:
1279:
1264:
1261:
1247:
1227:
1224:
1221:
1201:
1196:
1192:
1188:
1168:
1165:
1162:
1159:
1156:
1136:
1116:
1096:
1087:
1073:
1053:
1033:
1008:
983:
963:
943:
923:
898:
895:
892:
887:
883:
879:
870:
867:
864:
851:
837:
834:
826:
823:
811:
797:
794:
786:
774:
773:
772:
758:
738:
735:
732:
729:
726:
706:
686:
666:
646:
626:
606:
603:
600:
580:
568:
566:
564:
560:
556:
552:
548:
544:
543:Michael Rabin
539:
525:
505:
485:
465:
457:
452:
438:
418:
398:
395:
375:
355:
335:
332:
329:
326:
323:
320:
317:
314:
311:
308:
305:
302:
299:
296:
293:
290:
287:
284:
281:
278:
275:
255:
234:
231:
228:
225:
222:
201:
181:
161:
141:
121:
101:
81:
61:
52:
50:
46:
42:
38:
34:
30:
21:
4833:Nested stack
4776:Context-free
4701:Context-free
4662:Unrestricted
4518:
4506:
4482:
4442:
4411:
4378:
4371:
4340:
4334:
4324:
4318:
4312:(2): 143–172
4309:
4305:
4292:
4277:cite journal
4260:
4256:
4248:(Apr 1959).
4236:
4190:
4008:
3915:
3616:
3609:
3605:
3601:
3593:
3546:
3319:
3141:
3125:
3120:
3096:
3072:
3048:
3044:
3040:
3036:
2978:
2943:
2939:
2937:
2930:
2927:
2594:
2588:
2584:
2516:
2415:
2312:but none of
1803:be given by
1571:
1563:
1265:
1262:
1240:are also in
1088:
996:characters.
916:
572:
540:
453:
348:are also in
53:
48:
32:
26:
4842:restricted
4514:Anil Nerode
4246:Scott, Dana
4019:characters.
2391:Therefore,
2335:Therefore,
2332:were added.
4915:Categories
4502:0426.68001
4466:1169.68300
4430:1086.68074
4404:References
4382:. p.
4363:1161.68043
4302:Shamir, E.
3610:sufficient
3380:such that
2368:is not in
2029:for every
1976:such that
559:Eli Shamir
547:Dana Scott
4796:Star-free
4750:Positive
4740:Decidable
4675:Positive
4599:Languages
4163:and thus
3863:∧
3858:∗
3826:∈
3808:∪
3784:∨
3772:∨
3757:∧
3727:∈
3704:∗
3672:∈
3612:condition
3606:necessary
3528:≥
3440:≥
3404:≤
3255:≥
3173:≥
2161:≥
2082:≤
2040:≥
1961:≥
1925:≤
1641:Σ
1615:≥
1535:∈
1510:≥
1504:∀
1498:∧
1489:≤
1467:∧
1458:≥
1439:∧
1410:∗
1406:Σ
1402:∈
1384:∃
1375:⟹
1368:≥
1346:∈
1340:∀
1331:≥
1325:∃
1316:⟹
1291:∗
1287:Σ
1283:⊆
1277:∀
1225:≥
896:∈
868:≥
862:∀
835:≤
795:≥
604:≥
456:vacuously
4594:Grammars
4480:(1979).
4207:See also
3608:but not
3119:portion
3095:portion
3071:portion
2219:to give
2199:Pumping
2140:Because
4817:Decider
4791:Regular
4758:Indexed
4716:Regular
4683:Indexed
3132:NP hard
1301:regular
751:(i.e.,
248:, with
45:strings
4926:Lemmas
4869:Finite
4801:Finite
4646:Type-3
4637:Type-2
4619:Type-1
4613:Type-0
4526:
4500:
4490:
4464:
4454:
4428:
4418:
4390:
4361:
4351:
3811:
3497:is in
3099:and a
3037:abcbcd
2639:, let
2514:string
2058:Since
1737:above.
1713:, and
557:, and
49:pumped
31:, the
4827:PTIME
4448:77–83
4253:(PDF)
4229:Notes
4199:or a
3549:above
3234:with
2589:xyyyz
1901:with
37:lemma
35:is a
4574:and
4524:ISBN
4488:ISBN
4452:ISBN
4416:ISBN
4388:ISBN
4349:ISBN
4283:link
4191:The
3571:and
3455:and
3360:and
3075:, a
3049:abcd
2944:abcd
2940:abcd
2585:xyyz
1940:and
1763:Let
1675:Let
1214:for
1129:(in
1066:and
573:Let
545:and
194:and
4498:Zbl
4462:Zbl
4426:Zbl
4359:Zbl
4265:doi
4092:012
4073:013
3214:in
2517:xyz
2009:in
1783:in
659:in
114:in
4917::
4570::
4496:.
4476:;
4460:.
4450:.
4424:.
4386:.
4384:49
4357:.
4310:14
4308:,
4279:}}
4275:{{
4259:.
4255:.
4244:;
3419:,
3340:,
3134:.
3123:.
3097:bc
3045:ad
3041:bc
2979:bc
2587:,
1260:.
1086:.
565:.
553:,
538:.
174:,
4762:—
4720:—
4687:—
4652:—
4649:—
4643:—
4640:—
4634:—
4631:—
4628:—
4625:—
4622:—
4616:—
4560:e
4553:t
4546:v
4532:.
4504:.
4468:.
4432:.
4396:.
4365:.
4285:)
4267::
4261:3
4187:.
4171:L
4151:m
4148:4
4145:=
4142:i
4122:L
4100:i
4096:)
4089:(
4084:m
4081:3
4077:)
4070:(
4050:L
4030:L
4009:s
3995:5
3992:=
3989:p
3968:}
3965:3
3962:,
3959:2
3956:,
3953:1
3950:,
3947:0
3944:{
3924:L
3912:.
3896:}
3888:w
3877:7
3874:1
3854:}
3850:3
3847:,
3844:2
3841:,
3838:1
3835:,
3832:0
3829:{
3823:w
3820::
3817:w
3814:{
3799:}
3796:)
3793:w
3790:=
3787:x
3781:x
3778:=
3775:v
3769:w
3766:=
3763:v
3760:(
3754:}
3751:3
3748:,
3745:2
3742:,
3739:1
3736:,
3733:0
3730:{
3724:x
3721:,
3718:w
3715:,
3712:v
3709:;
3700:}
3696:3
3693:,
3690:2
3687:,
3684:1
3681:,
3678:0
3675:{
3669:y
3666:,
3663:u
3660::
3657:y
3654:x
3651:w
3648:v
3645:u
3642:{
3637:=
3632:L
3579:v
3559:u
3543:.
3531:0
3525:i
3505:L
3485:v
3482:z
3477:i
3473:y
3469:x
3466:u
3443:1
3436:|
3432:y
3428:|
3407:p
3400:|
3396:y
3393:x
3389:|
3368:z
3348:y
3328:x
3305:v
3302:z
3299:y
3296:x
3293:u
3290:=
3287:v
3284:w
3281:u
3258:p
3251:|
3247:w
3243:|
3222:L
3202:v
3199:w
3196:u
3176:1
3170:p
3150:L
3121:d
3107:z
3083:y
3073:a
3059:x
3021:1
3017:q
2994:1
2990:q
2963:1
2959:q
2913:y
2893:y
2873:y
2851:s
2847:q
2824:s
2820:q
2797:s
2793:q
2772:1
2769:+
2766:p
2746:p
2726:p
2704:p
2700:q
2696:,
2693:.
2690:.
2687:.
2684:,
2679:1
2675:q
2652:0
2648:q
2627:p
2607:p
2571:y
2549:t
2545:q
2541:=
2536:s
2532:q
2488:y
2468:y
2448:p
2428:p
2399:L
2376:L
2356:z
2351:2
2347:y
2343:x
2320:b
2300:a
2280:b
2260:a
2240:z
2235:2
2231:y
2227:x
2207:y
2196:.
2184:a
2164:1
2157:|
2153:y
2149:|
2137:.
2125:a
2105:y
2085:p
2078:|
2074:y
2071:x
2067:|
2055:.
2043:0
2037:i
2017:L
1997:z
1992:i
1988:y
1984:x
1964:1
1957:|
1953:y
1949:|
1928:p
1921:|
1917:y
1914:x
1910:|
1889:z
1886:y
1883:x
1880:=
1877:w
1866:.
1854:p
1832:p
1828:b
1822:p
1818:a
1814:=
1811:w
1791:L
1771:w
1748:p
1721:n
1701:z
1698:,
1695:y
1692:,
1689:x
1686:,
1683:w
1659:}
1656:b
1653:,
1650:a
1647:{
1644:=
1621:}
1618:0
1612:n
1609::
1604:n
1600:b
1594:n
1590:a
1586:{
1583:=
1580:L
1541:)
1538:L
1532:z
1527:n
1523:y
1519:x
1516:,
1513:0
1507:n
1501:(
1495:)
1492:p
1485:|
1481:y
1478:x
1474:|
1470:(
1464:)
1461:1
1454:|
1450:y
1446:|
1442:(
1436:)
1433:z
1430:y
1427:x
1424:=
1421:w
1418:(
1415:,
1399:z
1396:,
1393:y
1390:,
1387:x
1371:p
1364:|
1360:w
1356:|
1352:,
1349:L
1343:w
1337:,
1334:1
1328:p
1312:)
1309:L
1306:(
1296:,
1280:L
1248:L
1228:0
1222:n
1202:z
1197:n
1193:y
1189:x
1169:z
1166:y
1163:x
1160:=
1157:w
1137:L
1117:w
1097:L
1074:z
1054:x
1034:p
1013:|
1009:x
1005:|
984:p
964:y
944:L
924:y
902:)
899:L
893:z
888:n
884:y
880:x
877:(
874:)
871:0
865:n
859:(
838:p
831:|
827:y
824:x
820:|
798:1
791:|
787:y
783:|
759:w
739:z
736:y
733:x
730:=
727:w
707:p
699:(
687:p
667:L
647:w
627:L
607:1
601:p
581:L
526:p
506:L
486:L
466:p
439:w
419:p
399:y
396:x
376:y
356:L
336:.
333:.
330:.
327:,
324:z
321:y
318:y
315:y
312:x
309:,
306:z
303:y
300:y
297:x
294:,
291:z
288:y
285:x
282:,
279:z
276:x
256:y
235:z
232:y
229:x
226:=
223:w
214:(
202:z
182:y
162:x
142:p
122:L
102:w
82:p
62:L
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
