735:
393:
2070:
In formal language theory, questions about regular languages are usually decidable, but ones about context-free languages are often not. It is decidable whether such a language is finite, but not whether it contains every possible string, is regular, is unambiguous, or is equivalent to a language
79:, which makes these languages amenable to parsing. Further, for a given CFG, there is a direct way to produce a pushdown automaton for the grammar (and thereby the corresponding language), though going the other way (producing a grammar given an automaton) is not as direct.
730:{\displaystyle {\begin{aligned}\delta (q_{0},a,z)&=(q_{0},az)\\\delta (q_{0},a,a)&=(q_{0},aa)\\\delta (q_{0},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},b,a)&=(q_{1},\varepsilon )\\\delta (q_{1},\varepsilon ,z)&=(q_{f},\varepsilon )\end{aligned}}}
2786:
66:
Different context-free grammars can generate the same context-free language. Intrinsic properties of the language can be distinguished from extrinsic properties of a particular grammar by comparing multiple grammars that describe the language.
365:
2609:, but there does not exist a context-free grammar generating this language. So there exist context-sensitive languages which are not context-free. To prove that a given language is not context-free, one may employ the
1951:
1232:
Practical uses of context-free languages require also to produce a derivation tree that exhibits the structure that the grammar associates with the given string. The process of producing this tree is called
1878:
1997:
1801:
1724:
398:
908:
825:
2603:
985:
1060:
2660:
2181:
146:
910:. This set is context-free, since the union of two context-free languages is always context-free. But there is no way to unambiguously parse strings in the (non-context-free) subset
1242:
Formally, the set of all context-free languages is identical to the set of languages accepted by pushdown automata (PDA). Parser algorithms for context-free languages include the
2236:
2289:
1511:
2404:
1602:
1548:
207:
2891:
2060:
2516:
According to
Hopcroft, Motwani, Ullman (2003), many of the fundamental closure and (un)decidability properties of context-free languages were shown in the 1961 paper of
1443:
2502:
2128:
1141:
1470:
1368:
2655:
2034:
1323:
385:
1408:
2440:
2353:
2321:
3508:
2467:
1181:
1161:
1106:
1085:
219:
3428:
Autebert, Jean-Michel; Berstel, Jean; Boasson, Luc (1997). "Context-Free
Languages and Push-Down Automata". In G. Rozenberg; A. Salomaa (eds.).
1895:
3828:
3438:
3501:
2971:
2610:
1881:
3715:
3494:
3162:
1806:
1956:
3640:
1953:. In particular, context-free language cannot be closed under difference, since complement can be expressed by difference:
3133:
3730:
1729:
1652:
1254:
3338:
Yehoshua Bar-Hillel; Micha Asher Perles; Eli Shamir (1961). "On Formal
Properties of Simple Phrase-Structure Grammars".
3655:
830:
747:
2805:
3477:
3401:
2531:
913:
3823:
3808:
2926:
2781:{\displaystyle \delta (\mathrm {state} _{1},\mathrm {read} ,\mathrm {pop} )=(\mathrm {state} _{2},\mathrm {push} )}
1258:
1210:
1002:
3684:
3152:"A Proof that if L = L1 β© L2 where L1 is CFL and L2 is Regular then L is Context Free Which Does Not use PDA's"
2136:
90:
3852:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
1623:
741:
3701:
3626:
3798:
1518:
1450:
214:
3486:
2197:
1884:. As a consequence, context-free languages cannot be closed under complementation, as for any languages
1649:
The context-free languages are not closed under intersection. This can be seen by taking the languages
3694:
2606:
1269:
2252:
1477:
3870:
3619:
2374:
1612:
1563:
3771:
3766:
1523:
163:
2039:
1419:
3782:
3720:
3645:
2472:
2089:
1239:. Known parsers have a time complexity that is cubic in the size of the string that is parsed.
1111:
20:
3429:
1455:
1347:
3673:
2930:
2640:
2013:
1302:
1281:
1196:
370:
50:
1553:
1081:
The context-free nature of the language makes it simple to parse with a pushdown automaton.
3818:
3793:
3650:
3611:
2079:
1386:
43:
2416:
2329:
2297:
148:, the language of all non-empty even-length strings, the entire first halves of which are
8:
2618:
2517:
2075:
1188:
3040:
3803:
3745:
3689:
3018:
3016:
3014:
2963:
2945:
2452:
1297:
1166:
1146:
1091:
75:
The set of all context-free languages is identical to the set of languages accepted by
3128:
3004:
2911:
3538:
3473:
3466:
3397:
3390:
76:
53:, in particular, most arithmetic expressions are generated by context-free grammars.
33:
3151:
3011:
3787:
3740:
3707:
3553:
3449:
3123:
3000:
2967:
2955:
2906:
2614:
360:{\displaystyle M=(\{q_{0},q_{1},q_{f}\},\{a,b\},\{a,z\},\delta ,q_{0},z,\{q_{f}\})}
210:
3875:
3750:
3665:
3632:
3548:
3521:
3517:
39:
2504: ? Efficient polynomial-time algorithms for the membership problem are the
3761:
3543:
3525:
3461:
3337:
3318:
3108:
2931:"Fast Context-Free Grammar Parsing Requires Fast Boolean Matrix Multiplication"
1200:
1192:
3064:
1292:
are context-free languages, the following languages are context-free as well:
3864:
3846:
2509:
2505:
1342:
1247:
1243:
996:
3240:
3228:
3180:
1644:
3300:
3288:
2988:
3088:
3076:
2959:
1229:) CFG parsing, thus establishing some kind of lower bound for the latter.
3813:
3735:
3660:
3516:
3276:
3264:
3252:
3192:
3028:
1946:{\displaystyle A\cap B={\overline {{\overline {A}}\cup {\overline {B}}}}}
1381:
3340:
Zeitschrift fΓΌr
Phonetik, Sprachwissenschaft und Kommunikationsforschung
3216:
3052:
2871:
3369:
1262:
2991:(July 1965). "On the translation of languages from left to right".
2950:
2183: ? However, the intersection of a context-free language and a
2187:
language is context-free, hence the variant of the problem where
1235:
1076:
3333:
3331:
1892:, their intersection can be expressed by union and complement:
744:
CFLs. An example of an inherently ambiguous CFL is the union of
3776:
3328:
3845:
Each category of languages, except those marked by a , is a
3319:
John E. Hopcroft; Rajeev
Motwani; Jeffrey D. Ullman (2003).
740:
Unambiguous CFLs are a proper subset of all CFLs: there are
3392:
Introduction to
Automata Theory, Languages, and Computation
3321:
Introduction to
Automata Theory, Languages, and Computation
3350:
3109:"Note on the Boolean Properties of Context Free Languages"
2892:"General context-free recognition in less than cubic time"
2191:
is a regular grammar is decidable (see "Emptiness" below).
1645:
Nonclosure under intersection, complement, and difference
1257:
which are defined as the set of languages accepted by a
1873:{\displaystyle A\cap B=\{a^{n}b^{n}c^{n}\mid n\geq 0\}}
3427:
2523:
1992:{\displaystyle {\overline {L}}=\Sigma ^{*}\setminus L}
3159:
University of
Maryland Department of Computer Science
2663:
2643:
2534:
2475:
2455:
2419:
2377:
2332:
2300:
2255:
2200:
2139:
2092:
2042:
2016:
1959:
1898:
1809:
1803:, which are both context-free. Their intersection is
1732:
1655:
1566:
1526:
1480:
1458:
1422:
1389:
1350:
1305:
1253:
A special subclass of context-free languages are the
1169:
1149:
1114:
1094:
1005:
916:
833:
750:
396:
373:
222:
166:
93:
2242:
is a regular grammar is decidable, while that where
3370:"How to prove that a language is not context-free?"
2821:is given by the following production rules, taking
2010:is a regular language then both their intersection
1880:, which can be shown to be non-context-free by the
1796:{\displaystyle B=\{a^{m}b^{n}c^{n}\mid m,n\geq 0\}}
1719:{\displaystyle A=\{a^{n}b^{n}c^{m}\mid m,n\geq 0\}}
1221:) boolean matrix multiplication to be reducible to
3465:
3437:. Vol. 1. Springer-Verlag. pp. 111β174.
3389:
3106:
2780:
2649:
2597:
2496:
2461:
2434:
2398:
2347:
2315:
2283:
2230:
2175:
2122:
2054:
2028:
1991:
1945:
1872:
1795:
1718:
1596:
1542:
1505:
1464:
1437:
1402:
1362:
1317:
1272:as an alternative approach to grammar and parser.
1175:
1155:
1135:
1100:
1054:
987:which is the intersection of these two languages.
979:
902:
819:
729:
379:
359:
201:
140:
3454:The Mathematical Theory of Context-Free Languages
903:{\displaystyle \{a^{n}b^{n}c^{m}d^{m}|n,m>0\}}
820:{\displaystyle \{a^{n}b^{m}c^{m}d^{n}|n,m>0\}}
49:Context-free languages have many applications in
16:Formal language generated by context-free grammar
3862:
2238: ? Again, the variant of the problem where
1199:, thus inheriting its complexity upper bound of
3100:
2598:{\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}
980:{\displaystyle \{a^{n}b^{n}c^{n}d^{n}|n>0\}}
3388:Hopcroft, John E.; Ullman, Jeffrey D. (1979).
3387:
3356:
3306:
3294:
3282:
3270:
3258:
3246:
3234:
3222:
3198:
3186:
3094:
3082:
3070:
3058:
3046:
3034:
3022:
2877:
2806:Matrix multiplication#Computational complexity
152:'s, and the entire second halves of which are
3502:
1163:is the language generated by a given grammar
3049:, p. 131-132, Corollary of Theorem 6.2.
2592:
2535:
1867:
1822:
1790:
1739:
1713:
1662:
1591:
1567:
1284:under the following operations. That is, if
1055:{\displaystyle S\to SS~|~(S)~|~\varepsilon }
997:language of all properly matched parentheses
974:
917:
897:
834:
814:
751:
351:
338:
307:
295:
289:
277:
271:
232:
135:
100:
3824:Counter-free (with aperiodic finite monoid)
2804:) was the then-best known upper bound. See
3509:
3495:
3325:Here: Sect.7.6, p.304, and Sect.9.7, p.411
3468:Introduction to the Theory of Computation
3149:
3127:
2949:
2910:
2445:Membership: Given a context-free grammar
2409:Finiteness: Given a context-free grammar
3448:
3025:, p. 131, Corollary of Theorem 6.1.
2817:A context-free grammar for the language
2611:pumping lemma for context-free languages
2367:Emptiness: Given a context-free grammar
2176:{\displaystyle L(A)\cap L(B)=\emptyset }
1882:pumping lemma for context-free languages
141:{\displaystyle L=\{a^{n}b^{n}:n\geq 1\}}
3410:
3210:
2899:Journal of Computer and System Sciences
2889:
1280:The class of context-free languages is
1070:
61:
3863:
3716:Linear context-free rewriting language
3460:
2613:or a number of other methods, such as
2363:for arbitrary context-free languages:
3641:Linear context-free rewriting systems
3490:
3464:(1997). "2: Context-Free Languages".
2987:
1275:
1255:deterministic context-free languages
87:An example context-free language is
3472:. PWS Publishing. pp. 91β122.
3150:Beigel, Richard; Gasarch, William.
2925:
2524:Languages that are not context-free
13:
3849:of the category directly above it.
3421:
2808:for bound improvements since then.
2771:
2768:
2765:
2762:
2748:
2745:
2742:
2739:
2736:
2721:
2718:
2715:
2707:
2704:
2701:
2698:
2684:
2681:
2678:
2675:
2672:
2393:
2272:
2231:{\displaystyle L(A)\subseteq L(B)}
2170:
1974:
14:
3887:
3456:. New York, NY, USA: McGraw-Hill.
3073:, p. 142-144, Exercise 6.4c.
2890:Valiant, Leslie G. (April 1975).
2046:
1983:
3444:from the original on 2011-05-16.
3396:(1st ed.). Addison-Wesley.
3139:from the original on 2018-11-26.
2977:from the original on 2003-04-27.
2326:Ambiguity: is every grammar for
2284:{\displaystyle L(A)=\Sigma ^{*}}
1506:{\displaystyle \varphi ^{-1}(L)}
1259:deterministic pushdown automaton
990:
3362:
3312:
3249:, p. 203, Theorem 8.12(4).
3237:, p. 203, Theorem 8.12(2).
3204:
3189:, p. 203, Theorem 8.12(1).
3168:from the original on 2014-12-12
3143:
2811:
2399:{\displaystyle L(A)=\emptyset }
2065:
2006:is a context-free language and
1187:. Context-free recognition for
1084:Determining an instance of the
3380:
3309:, p. 137, Theorem 6.6(b).
3297:, p. 137, Theorem 6.6(a).
2981:
2919:
2883:
2790:
2775:
2731:
2725:
2667:
2631:
2579:
2491:
2485:
2429:
2423:
2387:
2381:
2342:
2336:
2310:
2304:
2265:
2259:
2225:
2219:
2210:
2204:
2164:
2158:
2149:
2143:
2117:
2111:
2102:
2096:
1597:{\displaystyle \{vu:uv\in L\}}
1500:
1494:
1432:
1426:
1130:
1124:
1042:
1035:
1029:
1022:
1009:
961:
878:
795:
720:
701:
691:
666:
656:
637:
627:
602:
592:
573:
563:
538:
528:
506:
496:
471:
461:
439:
429:
404:
354:
229:
186:
170:
1:
3129:10.1016/s0019-9958(60)90965-7
3097:, p. 142, Exercise 6.4a.
3085:, p. 142, Exercise 6.4b.
3037:, p. 142, Exercise 6.4d.
3005:10.1016/S0019-9958(65)90426-2
2912:10.1016/s0022-0000(75)80046-8
2864:
1543:{\displaystyle \varphi ^{-1}}
1065:
202:{\displaystyle S\to aSb~|~ab}
56:
3431:Handbook of Formal Languages
3285:, p. 206, Theorem 8.16.
3273:, p. 205, Theorem 8.15.
3261:, p. 203, Theorem 8.11.
3201:, p. 202, Theorem 8.10.
2246:is regular is generally not.
2062:are context-free languages.
2055:{\displaystyle L\setminus D}
1965:
1938:
1932:
1919:
999:is generated by the grammar
160:is generated by the grammar
7:
3225:, p. 135, Theorem 6.5.
3107:Stephen Scheinberg (1960).
3061:, p. 132, Theorem 6.3.
2880:, p. 100, Theorem 4.7.
2359:The following problems are
2074:The following problems are
1438:{\displaystyle \varphi (L)}
1195:to be reducible to boolean
82:
70:
10:
3892:
3731:Deterministic context-free
3656:Deterministic context-free
3357:Hopcroft & Ullman 1979
3307:Hopcroft & Ullman 1979
3295:Hopcroft & Ullman 1979
3283:Hopcroft & Ullman 1979
3271:Hopcroft & Ullman 1979
3259:Hopcroft & Ullman 1979
3247:Hopcroft & Ullman 1979
3235:Hopcroft & Ullman 1979
3223:Hopcroft & Ullman 1979
3199:Hopcroft & Ullman 1979
3187:Hopcroft & Ullman 1979
3095:Hopcroft & Ullman 1979
3083:Hopcroft & Ullman 1979
3071:Hopcroft & Ullman 1979
3059:Hopcroft & Ullman 1979
3047:Hopcroft & Ullman 1979
3035:Hopcroft & Ullman 1979
3023:Hopcroft & Ullman 1979
2878:Hopcroft & Ullman 1979
2657:'s arguments and results:
2607:context-sensitive language
2071:with a different grammar.
1270:parsing expression grammar
1074:
3842:
3804:Nondeterministic pushdown
3532:
2497:{\displaystyle w\in L(G)}
2123:{\displaystyle L(A)=L(B)}
1136:{\displaystyle w\in L(G)}
2624:
1465:{\displaystyle \varphi }
1363:{\displaystyle L\cdot P}
213:. It is accepted by the
3415:. ACM Monograph Series.
3116:Information and Control
2993:Information and Control
2650:{\displaystyle \delta }
2029:{\displaystyle L\cap D}
1318:{\displaystyle L\cup P}
1261:and can be parsed by a
387:is defined as follows:
380:{\displaystyle \delta }
209:. This language is not
3809:Deterministic pushdown
3685:Recursively enumerable
3411:Salomaa, Arto (1973).
2782:
2651:
2599:
2498:
2463:
2436:
2400:
2349:
2317:
2285:
2232:
2177:
2124:
2078:for arbitrarily given
2056:
2030:
1993:
1947:
1874:
1797:
1720:
1637:by a regular language
1607:the prefix closure of
1598:
1544:
1507:
1466:
1439:
1404:
1364:
1319:
1191:grammars was shown by
1177:
1157:
1137:
1102:
1088:; i.e. given a string
1056:
981:
904:
821:
731:
381:
361:
203:
142:
21:formal language theory
2960:10.1145/505241.505242
2825:as the start symbol:
2783:
2652:
2600:
2520:, Perles, and Shamir
2499:
2464:
2437:
2401:
2350:
2318:
2286:
2233:
2178:
2125:
2080:context-free grammars
2057:
2036:and their difference
2031:
1994:
1948:
1875:
1798:
1721:
1599:
1545:
1508:
1467:
1440:
1405:
1403:{\displaystyle L^{*}}
1365:
1320:
1197:matrix multiplication
1178:
1158:
1138:
1103:
1057:
982:
905:
822:
732:
382:
362:
204:
143:
51:programming languages
25:context-free language
3794:Tree stack automaton
3213:, p. 59, Theorem 6.7
2796:In Valiant's paper,
2661:
2641:
2532:
2473:
2453:
2435:{\displaystyle L(A)}
2417:
2375:
2348:{\displaystyle L(A)}
2330:
2316:{\displaystyle L(A)}
2298:
2253:
2198:
2137:
2090:
2040:
2014:
1957:
1896:
1807:
1730:
1653:
1564:
1524:
1519:inverse homomorphism
1478:
1456:
1420:
1387:
1348:
1303:
1167:
1147:
1112:
1108:, determine whether
1092:
1071:Context-free parsing
1003:
914:
831:
748:
742:inherently ambiguous
394:
371:
220:
164:
91:
62:Context-free grammar
44:context-free grammar
3702:range concatenation
3627:range concatenation
2323:a regular language?
1189:Chomsky normal form
1183:; is also known as
2853:. The grammar for
2778:
2647:
2595:
2510:Earley's Algorithm
2494:
2459:
2432:
2396:
2345:
2313:
2281:
2228:
2173:
2120:
2052:
2026:
1989:
1943:
1870:
1793:
1716:
1594:
1540:
1503:
1462:
1435:
1400:
1360:
1315:
1276:Closure properties
1248:Earley's Algorithm
1173:
1153:
1133:
1098:
1086:membership problem
1052:
977:
900:
817:
727:
725:
377:
357:
215:pushdown automaton
199:
138:
3858:
3857:
3837:
3836:
3799:Embedded pushdown
3695:Context-sensitive
3620:Context-sensitive
3554:Abstract machines
3539:Chomsky hierarchy
3450:Ginsburg, Seymour
3323:. Addison Wesley.
2462:{\displaystyle w}
2249:Universality: is
2133:Disjointness: is
1968:
1941:
1935:
1922:
1193:Leslie G. Valiant
1176:{\displaystyle G}
1156:{\displaystyle L}
1101:{\displaystyle w}
1048:
1040:
1028:
1020:
192:
184:
77:pushdown automata
31:), also called a
3883:
3871:Formal languages
3853:
3850:
3814:Visibly pushdown
3788:Thread automaton
3736:Visibly pushdown
3704:
3661:Visibly pushdown
3629:
3616:(no common name)
3535:
3534:
3522:formal languages
3511:
3504:
3497:
3488:
3487:
3483:
3471:
3457:
3445:
3443:
3436:
3416:
3413:Formal Languages
3407:
3395:
3374:
3373:
3366:
3360:
3354:
3348:
3347:
3335:
3326:
3324:
3316:
3310:
3304:
3298:
3292:
3286:
3280:
3274:
3268:
3262:
3256:
3250:
3244:
3238:
3232:
3226:
3220:
3214:
3208:
3202:
3196:
3190:
3184:
3178:
3177:
3175:
3173:
3167:
3156:
3147:
3141:
3140:
3138:
3131:
3113:
3104:
3098:
3092:
3086:
3080:
3074:
3068:
3062:
3056:
3050:
3044:
3038:
3032:
3026:
3020:
3009:
3008:
2985:
2979:
2978:
2976:
2953:
2935:
2929:(January 2002).
2923:
2917:
2916:
2914:
2896:
2887:
2881:
2875:
2858:
2815:
2809:
2794:
2788:
2787:
2785:
2784:
2779:
2774:
2757:
2756:
2751:
2724:
2710:
2693:
2692:
2687:
2656:
2654:
2653:
2648:
2635:
2619:Parikh's theorem
2604:
2602:
2601:
2596:
2582:
2577:
2576:
2567:
2566:
2557:
2556:
2547:
2546:
2503:
2501:
2500:
2495:
2468:
2466:
2465:
2460:
2441:
2439:
2438:
2433:
2405:
2403:
2402:
2397:
2354:
2352:
2351:
2346:
2322:
2320:
2319:
2314:
2290:
2288:
2287:
2282:
2280:
2279:
2237:
2235:
2234:
2229:
2194:Containment: is
2182:
2180:
2179:
2174:
2129:
2127:
2126:
2121:
2086:Equivalence: is
2061:
2059:
2058:
2053:
2035:
2033:
2032:
2027:
1998:
1996:
1995:
1990:
1982:
1981:
1969:
1961:
1952:
1950:
1949:
1944:
1942:
1937:
1936:
1928:
1923:
1915:
1912:
1879:
1877:
1876:
1871:
1854:
1853:
1844:
1843:
1834:
1833:
1802:
1800:
1799:
1794:
1771:
1770:
1761:
1760:
1751:
1750:
1725:
1723:
1722:
1717:
1694:
1693:
1684:
1683:
1674:
1673:
1615:of strings from
1611:(the set of all
1603:
1601:
1600:
1595:
1549:
1547:
1546:
1541:
1539:
1538:
1512:
1510:
1509:
1504:
1493:
1492:
1471:
1469:
1468:
1463:
1444:
1442:
1441:
1436:
1409:
1407:
1406:
1401:
1399:
1398:
1369:
1367:
1366:
1361:
1335:the reversal of
1324:
1322:
1321:
1316:
1182:
1180:
1179:
1174:
1162:
1160:
1159:
1154:
1142:
1140:
1139:
1134:
1107:
1105:
1104:
1099:
1061:
1059:
1058:
1053:
1046:
1045:
1038:
1026:
1025:
1018:
986:
984:
983:
978:
964:
959:
958:
949:
948:
939:
938:
929:
928:
909:
907:
906:
901:
881:
876:
875:
866:
865:
856:
855:
846:
845:
826:
824:
823:
818:
798:
793:
792:
783:
782:
773:
772:
763:
762:
736:
734:
733:
728:
726:
713:
712:
678:
677:
649:
648:
614:
613:
585:
584:
550:
549:
518:
517:
483:
482:
451:
450:
416:
415:
386:
384:
383:
378:
366:
364:
363:
358:
350:
349:
328:
327:
270:
269:
257:
256:
244:
243:
208:
206:
205:
200:
190:
189:
182:
159:
155:
151:
147:
145:
144:
139:
122:
121:
112:
111:
3891:
3890:
3886:
3885:
3884:
3882:
3881:
3880:
3861:
3860:
3859:
3854:
3851:
3844:
3838:
3833:
3755:
3699:
3678:
3624:
3605:
3528:
3526:formal grammars
3518:Automata theory
3515:
3480:
3462:Sipser, Michael
3441:
3434:
3424:
3422:Further reading
3419:
3404:
3383:
3378:
3377:
3368:
3367:
3363:
3355:
3351:
3336:
3329:
3317:
3313:
3305:
3301:
3293:
3289:
3281:
3277:
3269:
3265:
3257:
3253:
3245:
3241:
3233:
3229:
3221:
3217:
3209:
3205:
3197:
3193:
3185:
3181:
3171:
3169:
3165:
3154:
3148:
3144:
3136:
3111:
3105:
3101:
3093:
3089:
3081:
3077:
3069:
3065:
3057:
3053:
3045:
3041:
3033:
3029:
3021:
3012:
2986:
2982:
2974:
2933:
2924:
2920:
2894:
2888:
2884:
2876:
2872:
2867:
2862:
2861:
2816:
2812:
2795:
2791:
2761:
2752:
2735:
2734:
2714:
2697:
2688:
2671:
2670:
2662:
2659:
2658:
2642:
2639:
2638:
2636:
2632:
2627:
2578:
2572:
2568:
2562:
2558:
2552:
2548:
2542:
2538:
2533:
2530:
2529:
2526:
2474:
2471:
2470:
2454:
2451:
2450:
2418:
2415:
2414:
2376:
2373:
2372:
2331:
2328:
2327:
2299:
2296:
2295:
2294:Regularity: is
2275:
2271:
2254:
2251:
2250:
2199:
2196:
2195:
2138:
2135:
2134:
2091:
2088:
2087:
2068:
2041:
2038:
2037:
2015:
2012:
2011:
1977:
1973:
1960:
1958:
1955:
1954:
1927:
1914:
1913:
1911:
1897:
1894:
1893:
1849:
1845:
1839:
1835:
1829:
1825:
1808:
1805:
1804:
1766:
1762:
1756:
1752:
1746:
1742:
1731:
1728:
1727:
1689:
1685:
1679:
1675:
1669:
1665:
1654:
1651:
1650:
1647:
1565:
1562:
1561:
1531:
1527:
1525:
1522:
1521:
1485:
1481:
1479:
1476:
1475:
1457:
1454:
1453:
1421:
1418:
1417:
1394:
1390:
1388:
1385:
1384:
1349:
1346:
1345:
1304:
1301:
1300:
1278:
1209:). Conversely,
1168:
1165:
1164:
1148:
1145:
1144:
1113:
1110:
1109:
1093:
1090:
1089:
1079:
1073:
1068:
1041:
1021:
1004:
1001:
1000:
993:
960:
954:
950:
944:
940:
934:
930:
924:
920:
915:
912:
911:
877:
871:
867:
861:
857:
851:
847:
841:
837:
832:
829:
828:
794:
788:
784:
778:
774:
768:
764:
758:
754:
749:
746:
745:
724:
723:
708:
704:
694:
673:
669:
660:
659:
644:
640:
630:
609:
605:
596:
595:
580:
576:
566:
545:
541:
532:
531:
513:
509:
499:
478:
474:
465:
464:
446:
442:
432:
411:
407:
397:
395:
392:
391:
372:
369:
368:
345:
341:
323:
319:
265:
261:
252:
248:
239:
235:
221:
218:
217:
185:
165:
162:
161:
157:
153:
149:
117:
113:
107:
103:
92:
89:
88:
85:
73:
64:
59:
42:generated by a
36:type-2 language
17:
12:
11:
5:
3889:
3879:
3878:
3873:
3856:
3855:
3843:
3840:
3839:
3835:
3834:
3832:
3831:
3829:Acyclic finite
3826:
3821:
3816:
3811:
3806:
3801:
3796:
3790:
3785:
3780:
3779:Turing Machine
3774:
3772:Linear-bounded
3769:
3764:
3762:Turing machine
3758:
3756:
3754:
3753:
3748:
3743:
3738:
3733:
3728:
3723:
3721:Tree-adjoining
3718:
3713:
3710:
3705:
3697:
3692:
3687:
3681:
3679:
3677:
3676:
3671:
3668:
3663:
3658:
3653:
3648:
3646:Tree-adjoining
3643:
3638:
3635:
3630:
3622:
3617:
3614:
3608:
3606:
3604:
3603:
3600:
3597:
3594:
3591:
3588:
3585:
3582:
3579:
3576:
3573:
3570:
3567:
3564:
3560:
3557:
3556:
3551:
3546:
3541:
3533:
3530:
3529:
3514:
3513:
3506:
3499:
3491:
3485:
3484:
3478:
3458:
3446:
3423:
3420:
3418:
3417:
3408:
3402:
3384:
3382:
3379:
3376:
3375:
3361:
3349:
3327:
3311:
3299:
3287:
3275:
3263:
3251:
3239:
3227:
3215:
3211:Salomaa (1973)
3203:
3191:
3179:
3142:
3122:(4): 372β375.
3099:
3087:
3075:
3063:
3051:
3039:
3027:
3010:
2999:(6): 607β639.
2980:
2918:
2905:(2): 308β315.
2882:
2869:
2868:
2866:
2863:
2860:
2859:
2810:
2789:
2777:
2773:
2770:
2767:
2764:
2760:
2755:
2750:
2747:
2744:
2741:
2738:
2733:
2730:
2727:
2723:
2720:
2717:
2713:
2709:
2706:
2703:
2700:
2696:
2691:
2686:
2683:
2680:
2677:
2674:
2669:
2666:
2646:
2629:
2628:
2626:
2623:
2594:
2591:
2588:
2585:
2581:
2575:
2571:
2565:
2561:
2555:
2551:
2545:
2541:
2537:
2525:
2522:
2514:
2513:
2493:
2490:
2487:
2484:
2481:
2478:
2458:
2449:, and a word
2443:
2431:
2428:
2425:
2422:
2407:
2395:
2392:
2389:
2386:
2383:
2380:
2357:
2356:
2344:
2341:
2338:
2335:
2324:
2312:
2309:
2306:
2303:
2292:
2278:
2274:
2270:
2267:
2264:
2261:
2258:
2247:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2192:
2172:
2169:
2166:
2163:
2160:
2157:
2154:
2151:
2148:
2145:
2142:
2131:
2119:
2116:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2067:
2064:
2051:
2048:
2045:
2025:
2022:
2019:
1988:
1985:
1980:
1976:
1972:
1967:
1964:
1940:
1934:
1931:
1926:
1921:
1918:
1910:
1907:
1904:
1901:
1869:
1866:
1863:
1860:
1857:
1852:
1848:
1842:
1838:
1832:
1828:
1824:
1821:
1818:
1815:
1812:
1792:
1789:
1786:
1783:
1780:
1777:
1774:
1769:
1765:
1759:
1755:
1749:
1745:
1741:
1738:
1735:
1715:
1712:
1709:
1706:
1703:
1700:
1697:
1692:
1688:
1682:
1678:
1672:
1668:
1664:
1661:
1658:
1646:
1643:
1642:
1641:
1620:
1605:
1593:
1590:
1587:
1584:
1581:
1578:
1575:
1572:
1569:
1560:(the language
1554:circular shift
1550:
1537:
1534:
1530:
1502:
1499:
1496:
1491:
1488:
1484:
1472:
1461:
1434:
1431:
1428:
1425:
1414:
1397:
1393:
1378:
1359:
1356:
1353:
1339:
1333:
1314:
1311:
1308:
1277:
1274:
1172:
1152:
1132:
1129:
1126:
1123:
1120:
1117:
1097:
1075:Main article:
1072:
1069:
1067:
1064:
1051:
1044:
1037:
1034:
1031:
1024:
1017:
1014:
1011:
1008:
992:
989:
976:
973:
970:
967:
963:
957:
953:
947:
943:
937:
933:
927:
923:
919:
899:
896:
893:
890:
887:
884:
880:
874:
870:
864:
860:
854:
850:
844:
840:
836:
816:
813:
810:
807:
804:
801:
797:
791:
787:
781:
777:
771:
767:
761:
757:
753:
738:
737:
722:
719:
716:
711:
707:
703:
700:
697:
695:
693:
690:
687:
684:
681:
676:
672:
668:
665:
662:
661:
658:
655:
652:
647:
643:
639:
636:
633:
631:
629:
626:
623:
620:
617:
612:
608:
604:
601:
598:
597:
594:
591:
588:
583:
579:
575:
572:
569:
567:
565:
562:
559:
556:
553:
548:
544:
540:
537:
534:
533:
530:
527:
524:
521:
516:
512:
508:
505:
502:
500:
498:
495:
492:
489:
486:
481:
477:
473:
470:
467:
466:
463:
460:
457:
454:
449:
445:
441:
438:
435:
433:
431:
428:
425:
422:
419:
414:
410:
406:
403:
400:
399:
376:
356:
353:
348:
344:
340:
337:
334:
331:
326:
322:
318:
315:
312:
309:
306:
303:
300:
297:
294:
291:
288:
285:
282:
279:
276:
273:
268:
264:
260:
255:
251:
247:
242:
238:
234:
231:
228:
225:
198:
195:
188:
181:
178:
175:
172:
169:
137:
134:
131:
128:
125:
120:
116:
110:
106:
102:
99:
96:
84:
81:
72:
69:
63:
60:
58:
55:
15:
9:
6:
4:
3:
2:
3888:
3877:
3874:
3872:
3869:
3868:
3866:
3848:
3847:proper subset
3841:
3830:
3827:
3825:
3822:
3820:
3817:
3815:
3812:
3810:
3807:
3805:
3802:
3800:
3797:
3795:
3791:
3789:
3786:
3784:
3781:
3778:
3775:
3773:
3770:
3768:
3765:
3763:
3760:
3759:
3757:
3752:
3749:
3747:
3744:
3742:
3739:
3737:
3734:
3732:
3729:
3727:
3724:
3722:
3719:
3717:
3714:
3711:
3709:
3706:
3703:
3698:
3696:
3693:
3691:
3688:
3686:
3683:
3682:
3680:
3675:
3674:Non-recursive
3672:
3669:
3667:
3664:
3662:
3659:
3657:
3654:
3652:
3649:
3647:
3644:
3642:
3639:
3636:
3634:
3631:
3628:
3623:
3621:
3618:
3615:
3613:
3610:
3609:
3607:
3601:
3598:
3595:
3592:
3589:
3586:
3583:
3580:
3577:
3574:
3571:
3568:
3565:
3562:
3561:
3559:
3558:
3555:
3552:
3550:
3547:
3545:
3542:
3540:
3537:
3536:
3531:
3527:
3523:
3519:
3512:
3507:
3505:
3500:
3498:
3493:
3492:
3489:
3481:
3479:0-534-94728-X
3475:
3470:
3469:
3463:
3459:
3455:
3451:
3447:
3440:
3433:
3432:
3426:
3425:
3414:
3409:
3405:
3403:9780201029888
3399:
3394:
3393:
3386:
3385:
3371:
3365:
3358:
3353:
3346:(2): 143β172.
3345:
3341:
3334:
3332:
3322:
3315:
3308:
3303:
3296:
3291:
3284:
3279:
3272:
3267:
3260:
3255:
3248:
3243:
3236:
3231:
3224:
3219:
3212:
3207:
3200:
3195:
3188:
3183:
3164:
3160:
3153:
3146:
3135:
3130:
3125:
3121:
3117:
3110:
3103:
3096:
3091:
3084:
3079:
3072:
3067:
3060:
3055:
3048:
3043:
3036:
3031:
3024:
3019:
3017:
3015:
3006:
3002:
2998:
2994:
2990:
2984:
2973:
2969:
2965:
2961:
2957:
2952:
2947:
2943:
2939:
2932:
2928:
2922:
2913:
2908:
2904:
2900:
2893:
2886:
2879:
2874:
2870:
2857:is analogous.
2856:
2852:
2848:
2844:
2840:
2836:
2832:
2828:
2824:
2820:
2814:
2807:
2803:
2799:
2793:
2758:
2753:
2728:
2711:
2694:
2689:
2664:
2644:
2634:
2630:
2622:
2620:
2616:
2615:Ogden's lemma
2612:
2608:
2589:
2586:
2583:
2573:
2569:
2563:
2559:
2553:
2549:
2543:
2539:
2521:
2519:
2511:
2507:
2506:CYK algorithm
2488:
2482:
2479:
2476:
2456:
2448:
2444:
2426:
2420:
2412:
2408:
2390:
2384:
2378:
2370:
2366:
2365:
2364:
2362:
2339:
2333:
2325:
2307:
2301:
2293:
2276:
2268:
2262:
2256:
2248:
2245:
2241:
2222:
2216:
2213:
2207:
2201:
2193:
2190:
2186:
2167:
2161:
2155:
2152:
2146:
2140:
2132:
2114:
2108:
2105:
2099:
2093:
2085:
2084:
2083:
2081:
2077:
2072:
2063:
2049:
2043:
2023:
2020:
2017:
2009:
2005:
2000:
1986:
1978:
1970:
1962:
1929:
1924:
1916:
1908:
1905:
1902:
1899:
1891:
1887:
1883:
1864:
1861:
1858:
1855:
1850:
1846:
1840:
1836:
1830:
1826:
1819:
1816:
1813:
1810:
1787:
1784:
1781:
1778:
1775:
1772:
1767:
1763:
1757:
1753:
1747:
1743:
1736:
1733:
1710:
1707:
1704:
1701:
1698:
1695:
1690:
1686:
1680:
1676:
1670:
1666:
1659:
1656:
1640:
1636:
1632:
1628:
1625:
1621:
1618:
1614:
1610:
1606:
1588:
1585:
1582:
1579:
1576:
1573:
1570:
1559:
1555:
1551:
1535:
1532:
1528:
1520:
1516:
1497:
1489:
1486:
1482:
1473:
1459:
1452:
1448:
1429:
1423:
1415:
1413:
1395:
1391:
1383:
1379:
1377:
1373:
1357:
1354:
1351:
1344:
1343:concatenation
1340:
1338:
1334:
1332:
1328:
1312:
1309:
1306:
1299:
1295:
1294:
1293:
1291:
1287:
1283:
1273:
1271:
1266:
1264:
1260:
1256:
1251:
1249:
1245:
1244:CYK algorithm
1240:
1238:
1237:
1230:
1228:
1224:
1220:
1216:
1212:
1208:
1204:
1203:
1198:
1194:
1190:
1186:
1170:
1150:
1127:
1121:
1118:
1115:
1095:
1087:
1082:
1078:
1063:
1049:
1032:
1015:
1012:
1006:
998:
991:Dyck language
988:
971:
968:
965:
955:
951:
945:
941:
935:
931:
925:
921:
894:
891:
888:
885:
882:
872:
868:
862:
858:
852:
848:
842:
838:
811:
808:
805:
802:
799:
789:
785:
779:
775:
769:
765:
759:
755:
743:
717:
714:
709:
705:
698:
696:
688:
685:
682:
679:
674:
670:
663:
653:
650:
645:
641:
634:
632:
624:
621:
618:
615:
610:
606:
599:
589:
586:
581:
577:
570:
568:
560:
557:
554:
551:
546:
542:
535:
525:
522:
519:
514:
510:
503:
501:
493:
490:
487:
484:
479:
475:
468:
458:
455:
452:
447:
443:
436:
434:
426:
423:
420:
417:
412:
408:
401:
390:
389:
388:
374:
346:
342:
335:
332:
329:
324:
320:
316:
313:
310:
304:
301:
298:
292:
286:
283:
280:
274:
266:
262:
258:
253:
249:
245:
240:
236:
226:
223:
216:
212:
196:
193:
179:
176:
173:
167:
132:
129:
126:
123:
118:
114:
108:
104:
97:
94:
80:
78:
68:
54:
52:
47:
45:
41:
37:
35:
30:
26:
22:
3783:Nested stack
3726:Context-free
3725:
3651:Context-free
3612:Unrestricted
3467:
3453:
3430:
3412:
3391:
3364:
3352:
3343:
3339:
3320:
3314:
3302:
3290:
3278:
3266:
3254:
3242:
3230:
3218:
3206:
3194:
3182:
3170:. Retrieved
3158:
3145:
3119:
3115:
3102:
3090:
3078:
3066:
3054:
3042:
3030:
2996:
2992:
2989:Knuth, D. E.
2983:
2941:
2937:
2927:Lee, Lillian
2921:
2902:
2898:
2885:
2873:
2854:
2850:
2846:
2842:
2838:
2834:
2830:
2826:
2822:
2818:
2813:
2801:
2797:
2792:
2633:
2527:
2515:
2446:
2410:
2368:
2360:
2358:
2243:
2239:
2188:
2184:
2073:
2069:
2066:Decidability
2007:
2003:
2002:However, if
2001:
1889:
1885:
1648:
1638:
1634:
1630:
1626:
1616:
1608:
1557:
1514:
1451:homomorphism
1446:
1411:
1375:
1371:
1336:
1330:
1326:
1289:
1285:
1279:
1267:
1263:LR(k) parser
1252:
1241:
1234:
1231:
1226:
1222:
1218:
1214:
1206:
1201:
1184:
1083:
1080:
994:
739:
86:
74:
65:
48:
32:
28:
24:
18:
3792:restricted
3381:Works cited
2944:(1): 1β15.
2637:meaning of
2076:undecidable
1382:Kleene star
1211:Lillian Lee
1185:recognition
3865:Categories
2951:cs/0112018
2865:References
2518:Bar-Hillel
2355:ambiguous?
1474:the image
1416:the image
1213:has shown
1066:Properties
57:Background
3746:Star-free
3700:Positive
3690:Decidable
3625:Positive
3549:Languages
2665:δ
2645:δ
2480:∈
2394:∅
2361:decidable
2277:∗
2273:Σ
2214:⊆
2171:∅
2153:∩
2082:A and B:
2047:∖
2021:∩
1984:∖
1979:∗
1975:Σ
1966:¯
1939:¯
1933:¯
1925:∪
1920:¯
1903:∩
1862:≥
1856:∣
1814:∩
1785:≥
1773:∣
1708:≥
1696:∣
1586:∈
1533:−
1529:φ
1517:under an
1487:−
1483:φ
1460:φ
1424:φ
1396:∗
1355:⋅
1310:∪
1268:See also
1119:∈
1050:ε
1010:→
718:ε
683:ε
664:δ
654:ε
600:δ
590:ε
536:δ
469:δ
402:δ
375:δ
314:δ
171:→
130:≥
3544:Grammars
3452:(1966).
3439:Archived
3163:Archived
3134:Archived
2972:Archived
2528:The set
1624:quotient
1613:prefixes
1449:under a
83:Examples
71:Automata
40:language
3767:Decider
3741:Regular
3708:Indexed
3666:Regular
3633:Indexed
3172:June 6,
2968:1243491
2469:, does
2442:finite?
2406: ?
2185:regular
1236:parsing
1077:Parsing
211:regular
46:(CFG).
38:, is a
34:Chomsky
3876:Syntax
3819:Finite
3751:Finite
3596:Type-3
3587:Type-2
3569:Type-1
3563:Type-0
3476:
3400:
2966:
1282:closed
1143:where
1047:
1039:
1027:
1019:
367:where
191:
183:
3777:PTIME
3442:(PDF)
3435:(PDF)
3166:(PDF)
3155:(PDF)
3137:(PDF)
3112:(PDF)
2975:(PDF)
2964:S2CID
2946:arXiv
2938:J ACM
2934:(PDF)
2895:(PDF)
2625:Notes
2605:is a
2413:, is
2371:, is
1298:union
827:with
23:, a
3524:and
3474:ISBN
3398:ISBN
3174:2020
2587:>
2508:and
1888:and
1726:and
1622:the
1552:the
1380:the
1374:and
1341:the
1329:and
1296:the
1288:and
1246:and
995:The
969:>
892:>
809:>
156:'s.
3124:doi
3001:doi
2956:doi
2907:doi
2847:aTb
2835:aTb
2617:or
1633:of
1556:of
1513:of
1445:of
1410:of
1370:of
1325:of
29:CFL
19:In
3867::
3520::
3344:14
3342:.
3330:^
3161:.
3157:.
3132:.
3118:.
3114:.
3013:^
2995:.
2970:.
2962:.
2954:.
2942:49
2940:.
2936:.
2903:10
2901:.
2897:.
2849:|
2845:β
2841:;
2837:|
2833:|
2831:Sc
2829:β
2621:.
1999:.
1265:.
1250:.
1062:.
3712:β
3670:β
3637:β
3602:β
3599:β
3593:β
3590:β
3584:β
3581:β
3578:β
3575:β
3572:β
3566:β
3510:e
3503:t
3496:v
3482:.
3406:.
3372:.
3359:.
3176:.
3126::
3120:3
3007:.
3003::
2997:8
2958::
2948::
2915:.
2909::
2855:B
2851:Ξ΅
2843:T
2839:Ξ΅
2827:S
2823:S
2819:A
2802:n
2800:(
2798:O
2776:)
2772:h
2769:s
2766:u
2763:p
2759:,
2754:2
2749:e
2746:t
2743:a
2740:t
2737:s
2732:(
2729:=
2726:)
2722:p
2719:o
2716:p
2712:,
2708:d
2705:a
2702:e
2699:r
2695:,
2690:1
2685:e
2682:t
2679:a
2676:t
2673:s
2668:(
2593:}
2590:0
2584:n
2580:|
2574:n
2570:d
2564:n
2560:c
2554:n
2550:b
2544:n
2540:a
2536:{
2512:.
2492:)
2489:G
2486:(
2483:L
2477:w
2457:w
2447:G
2430:)
2427:A
2424:(
2421:L
2411:A
2391:=
2388:)
2385:A
2382:(
2379:L
2369:A
2343:)
2340:A
2337:(
2334:L
2311:)
2308:A
2305:(
2302:L
2291:?
2269:=
2266:)
2263:A
2260:(
2257:L
2244:A
2240:B
2226:)
2223:B
2220:(
2217:L
2211:)
2208:A
2205:(
2202:L
2189:B
2168:=
2165:)
2162:B
2159:(
2156:L
2150:)
2147:A
2144:(
2141:L
2130:?
2118:)
2115:B
2112:(
2109:L
2106:=
2103:)
2100:A
2097:(
2094:L
2050:D
2044:L
2024:D
2018:L
2008:D
2004:L
1987:L
1971:=
1963:L
1930:B
1917:A
1909:=
1906:B
1900:A
1890:B
1886:A
1868:}
1865:0
1859:n
1851:n
1847:c
1841:n
1837:b
1831:n
1827:a
1823:{
1820:=
1817:B
1811:A
1791:}
1788:0
1782:n
1779:,
1776:m
1768:n
1764:c
1758:n
1754:b
1748:m
1744:a
1740:{
1737:=
1734:B
1714:}
1711:0
1705:n
1702:,
1699:m
1691:m
1687:c
1681:n
1677:b
1671:n
1667:a
1663:{
1660:=
1657:A
1639:R
1635:L
1631:R
1629:/
1627:L
1619:)
1617:L
1609:L
1604:)
1592:}
1589:L
1583:v
1580:u
1577::
1574:u
1571:v
1568:{
1558:L
1536:1
1515:L
1501:)
1498:L
1495:(
1490:1
1447:L
1433:)
1430:L
1427:(
1412:L
1392:L
1376:P
1372:L
1358:P
1352:L
1337:L
1331:P
1327:L
1313:P
1307:L
1290:P
1286:L
1227:n
1225:(
1223:O
1219:n
1217:(
1215:O
1207:n
1205:(
1202:O
1171:G
1151:L
1131:)
1128:G
1125:(
1122:L
1116:w
1096:w
1043:|
1036:)
1033:S
1030:(
1023:|
1016:S
1013:S
1007:S
975:}
972:0
966:n
962:|
956:n
952:d
946:n
942:c
936:n
932:b
926:n
922:a
918:{
898:}
895:0
889:m
886:,
883:n
879:|
873:m
869:d
863:m
859:c
853:n
849:b
843:n
839:a
835:{
815:}
812:0
806:m
803:,
800:n
796:|
790:n
786:d
780:m
776:c
770:m
766:b
760:n
756:a
752:{
721:)
715:,
710:f
706:q
702:(
699:=
692:)
689:z
686:,
680:,
675:1
671:q
667:(
657:)
651:,
646:1
642:q
638:(
635:=
628:)
625:a
622:,
619:b
616:,
611:1
607:q
603:(
593:)
587:,
582:1
578:q
574:(
571:=
564:)
561:a
558:,
555:b
552:,
547:0
543:q
539:(
529:)
526:a
523:a
520:,
515:0
511:q
507:(
504:=
497:)
494:a
491:,
488:a
485:,
480:0
476:q
472:(
462:)
459:z
456:a
453:,
448:0
444:q
440:(
437:=
430:)
427:z
424:,
421:a
418:,
413:0
409:q
405:(
355:)
352:}
347:f
343:q
339:{
336:,
333:z
330:,
325:0
321:q
317:,
311:,
308:}
305:z
302:,
299:a
296:{
293:,
290:}
287:b
284:,
281:a
278:{
275:,
272:}
267:f
263:q
259:,
254:1
250:q
246:,
241:0
237:q
233:{
230:(
227:=
224:M
197:b
194:a
187:|
180:b
177:S
174:a
168:S
158:L
154:b
150:a
136:}
133:1
127:n
124::
119:n
115:b
109:n
105:a
101:{
98:=
95:L
27:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.