2323:
2038:
1567:
39:
represented by multiple rules for a single nonterminal symbol, which is the only logical connective expressible in context-free grammars. Conjunction can be used, in particular, to specify intersection of languages. A further extension of conjunctive grammars known as
2420:
Though the expressive power of conjunctive grammars is greater than those of context-free grammars, conjunctive grammars retain some of the latter. Most importantly, there are generalizations of the main context-free parsing algorithms, including the linear-time
2318:{\displaystyle S\Rightarrow (AB\&DC)\Rightarrow (aAB\&DC)\Rightarrow (aB\&DC)\Rightarrow (abBc\&DC)\Rightarrow (abc\&DC)\Rightarrow (abc\&aDbC)\Rightarrow (abc\&abC)\Rightarrow (abc\&abcC)\Rightarrow (abc\&abc)\Rightarrow abc}
1446:
855:
963:
1640:
1060:
1186:
879:
711:
537:
763:
104:
1299:
1441:
629:
2631:
2406:
1799:
2026:
1933:
1978:
1885:
768:
1234:
1840:
1693:
1386:
420:
998:
1346:
1107:
2700:
This paper supersedes the earlier surveys, "An overview of conjunctive grammars" (Bulletin of the EATCS, 2004) and "Nine open problems for conjunctive and
Boolean grammars"
319:
292:
181:
154:
2445:
A property that is undecidable already for context-free languages or finite intersections of them, must be undecidable also for conjunctive grammars; these include:
265:
201:
453:
860:
Two equivalent formal definitions of the language specified by a conjunctive grammar exist. One definition is based upon representing the grammar as a system of
577:
557:
367:
339:
245:
221:
127:
1572:
2409:
2506:(SAPDA). They proved it to be equivalent to conjunctive grammars in the same way as nondeterministic PDAs are equivalent to context-free grammars.
1562:{\displaystyle \exists k\geq 1\,\exists \,u_{1},\cdots ,u_{k}\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}
1007:
1112:
2595:
664:
490:
716:
463:. Each variable represents a different type of phrase or clause in the sentence. Variables are also sometimes called syntactic categories.
2664:
2578:
Aizikowitz, Tamar; Kaminski, Michael (2011). "LR(0) Conjunctive
Grammars and Deterministic Synchronized Alternating Pushdown Automata".
57:
224:
477:, which make up the actual content of the sentence. The set of terminals is the alphabet of the language defined by the grammar
2480:, suffix, and substring. Closure under complement and under ε-free string homomorphism are still open problems (as of 2001).
1239:
1401:
582:
2331:
1706:
649:
is the start variable (or start symbol), used to represent the whole sentence (or program). It must be an element of
1985:
1892:
1940:
1847:
2680:
Alexander
Okhotin (2013). "Conjunctive and Boolean grammars: The true general case of the context-free grammars".
850:{\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\ |\ \beta _{1}\&\ldots \&\beta _{n}}
2739:
868:
generative definition of the context-free grammars using rewriting of terms over conjunction and concatenation.
864:
with union, intersection and concatenation and considering its least solution. The other definition generalizes
2422:
1194:
2682:
1807:
2458:
28:
1648:
1355:
958:{\displaystyle u,v\in (V\cup \Sigma \cup \{{\text{“(”}},{\text{“}}\&{\text{”}},{\text{“)”}}\})^{*}}
375:
2531:
Given two conjunctive grammars, is the first's generated language a subset of / equal to the second's?
976:
1304:
1065:
657:
It is common to list all right-hand sides for the same left-hand side on the same line, using | (the
2473:
36:
32:
2624:
2503:
297:
270:
159:
132:
2522:
Given a conjunctive grammar, is its generated language empty / finite / regular / context-free?
2601:
2591:
2499:
2487:
861:
2672:
250:
186:
2715:
2691:
2583:
2454:
432:
2450:
41:
24:
2446:
2434:
562:
542:
352:
324:
230:
206:
112:
20:
2733:
2477:
2465:
2430:
2553:
2724:
865:
1635:{\displaystyle S=\,u_{1}\Rightarrow u_{2}\Rightarrow \cdots \Rightarrow u_{k}\,=w}
2695:
2587:
2483:
The expressive power of grammars over a one-letter alphabet has been researched.
2706:
Jeż, Artur (2008). "Conjunctive grammars generate non-regular unary languages".
2469:
658:
2719:
2426:
2605:
35:
operation. Besides explicit conjunction, conjunctive grammars allow implicit
1055:{\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}\in R}
2647:
2464:
The family of conjunctive languages is closed under union, intersection,
1181:{\displaystyle v\,=u_{1}(\alpha _{1}\&\ldots \&\alpha _{m})u_{2}}
45:
2582:. Lecture Notes in Computer Science. Vol. 6651. pp. 345–358.
706:{\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}
532:{\displaystyle A\rightarrow \alpha _{1}\&\ldots \&\alpha _{m}}
758:{\displaystyle A\rightarrow \beta _{1}\&\ldots \&\beta _{n}}
370:
227:
respectively). Informally, such a rule asserts that every string
267:
that satisfies each of the syntactical conditions represented by
99:{\displaystyle A\to \alpha _{1}\And \ldots \And \alpha _{m}}
2632:
International
Conference on Developments in Language Theory
2625:"Conjunctive grammars generate non-regular unary languages"
2665:"Nine open problems for conjunctive and Boolean grammars"
2708:
International
Journal of Foundations of Computer Science
2334:
2041:
1988:
1943:
1895:
1850:
1810:
1709:
1651:
1575:
1449:
1404:
1358:
1307:
1294:{\displaystyle u\,=u_{1}(w\&\ldots \&w)u_{2}}
1242:
1197:
1115:
1068:
1010:
979:
882:
771:
719:
667:
585:
565:
545:
493:
435:
378:
355:
327:
300:
273:
253:
233:
209:
189:
162:
135:
115:
60:
2437:
algorithm running as fast as matrix multiplication.
27:
theory. They extend the basic type of grammars, the
1436:{\displaystyle S\ {\stackrel {*}{\Rightarrow }}\ w}
51:The rules of a conjunctive grammar are of the form
2648:"Alexander Okhotin's page on conjunctive grammars"
2498:Aizikowitz and Kaminski introduced a new class of
2408:. The language is not context-free, proved by the
2400:
2317:
2020:
1972:
1927:
1879:
1834:
1793:
1687:
1634:
1561:
1435:
1380:
1340:
1293:
1228:
1180:
1101:
1054:
992:
957:
849:
757:
705:
624:{\displaystyle \alpha _{i}\in (V\cup \Sigma )^{*}}
623:
571:
551:
531:
447:
414:
361:
333:
313:
286:
259:
239:
215:
195:
175:
148:
121:
98:
487:is a finite set of productions, each of the form
2561:Journal of Automata, Languages and Combinatorics
2401:{\displaystyle L(G)=\{a^{n}b^{n}c^{n}:n\geq 0\}}
1794:{\displaystyle G=(\{S,A,B,C,D\},\{a,b,c\},R,S)}
2021:{\displaystyle D\rightarrow aDb\ |\ \epsilon }
1928:{\displaystyle B\rightarrow bBc\ |\ \epsilon }
1973:{\displaystyle C\rightarrow cC\ |\ \epsilon }
1880:{\displaystyle A\rightarrow aA\ |\ \epsilon }
321:therefore satisfies the condition defined by
8:
2486:This work provided a basis for the study of
2395:
2350:
1773:
1755:
1749:
1719:
1546:
1514:
942:
910:
2580:Computer Science – Theory and Applications
2504:synchronized alternating pushdown automata
2494:Synchronized alternating pushdown automata
2377:
2367:
2357:
2333:
2040:
2032:is conjunctive. A typical derivation is
2007:
1987:
1959:
1942:
1914:
1894:
1866:
1849:
1809:
1708:
1650:
1625:
1619:
1600:
1587:
1582:
1574:
1553:
1541:
1533:
1525:
1517:
1490:
1471:
1466:
1462:
1448:
1419:
1414:
1412:
1411:
1403:
1369:
1357:
1332:
1319:
1311:
1306:
1285:
1254:
1246:
1241:
1220:
1196:
1172:
1159:
1140:
1127:
1119:
1114:
1093:
1080:
1072:
1067:
1040:
1021:
1009:
989:
978:
949:
937:
929:
921:
913:
881:
841:
822:
810:
801:
782:
770:
749:
730:
718:
697:
678:
666:
615:
590:
584:
564:
544:
523:
504:
492:
434:
377:
354:
326:
305:
299:
278:
272:
252:
232:
208:
188:
167:
161:
140:
134:
114:
90:
71:
59:
2410:pumping lemma for context-free languages
1695:is the set of all strings it generates.
1229:{\displaystyle w\in (V\cup \Sigma )^{*}}
2544:
2515:
1835:{\displaystyle S\rightarrow AB\&DC}
7:
2288:
2255:
2225:
2192:
2165:
2138:
2108:
2084:
2057:
1823:
1667:
1530:
1508:
1463:
1450:
1366:
1272:
1266:
1213:
1152:
1146:
1033:
1027:
926:
904:
834:
828:
794:
788:
742:
736:
690:
684:
608:
516:
510:
394:
254:
190:
83:
77:
14:
1688:{\displaystyle G=(V,\Sigma ,R,S)}
1381:{\displaystyle w\in \Sigma ^{*},}
415:{\displaystyle G=(V,\Sigma ,R,S)}
183:are strings formed of symbols in
993:{\displaystyle u\Rightarrow v\,}
225:terminal and nonterminal symbols
1341:{\displaystyle v\,=u_{1}wu_{2}}
1102:{\displaystyle u\,=u_{1}Au_{2}}
2725:Technical report version (pdf)
2344:
2338:
2303:
2300:
2276:
2273:
2270:
2243:
2240:
2237:
2213:
2210:
2207:
2180:
2177:
2174:
2153:
2150:
2147:
2123:
2120:
2117:
2099:
2096:
2093:
2072:
2069:
2066:
2048:
2045:
2008:
1992:
1960:
1947:
1915:
1899:
1867:
1854:
1814:
1788:
1716:
1682:
1658:
1612:
1606:
1593:
1550:
1499:
1415:
1278:
1260:
1217:
1204:
1165:
1133:
1014:
983:
946:
895:
811:
775:
723:
671:
612:
599:
497:
429:is a finite set; each element
409:
385:
64:
1:
2461:, inclusion and equivalence.
44:additionally allows explicit
2696:10.1016/j.cosrev.2013.06.001
2630:(Slides of talk held at the
2588:10.1007/978-3-642-20712-9_27
314:{\displaystyle \alpha _{m}}
287:{\displaystyle \alpha _{1}}
176:{\displaystyle \alpha _{m}}
149:{\displaystyle \alpha _{1}}
2756:
2663:Alexander Okhotin (2007).
2552:Alexander Okhotin (2001).
1645:The language of a grammar
661:) to separate them. Rules
2720:10.1142/S012905410800584X
1191:or there exists a string
2490:of a more general form.
872:Definition by derivation
765:can hence be written as
2683:Computer Science Review
1004:either there is a rule
260:{\displaystyle \Sigma }
196:{\displaystyle \Sigma }
2554:"Conjunctive Grammars"
2441:Theoretical properties
2402:
2319:
2022:
1974:
1929:
1881:
1836:
1795:
1689:
1636:
1563:
1437:
1382:
1342:
1295:
1230:
1182:
1103:
1056:
994:
959:
851:
759:
707:
625:
573:
553:
533:
449:
448:{\displaystyle v\in V}
416:
363:
349:A conjunctive grammar
335:
315:
288:
261:
241:
217:
197:
177:
150:
123:
100:
2669:Bulletin of the EATCS
2403:
2328:It can be shown that
2320:
2023:
1975:
1930:
1882:
1837:
1796:
1690:
1637:
1564:
1438:
1383:
1343:
1296:
1231:
1183:
1104:
1057:
995:
960:
852:
760:
708:
626:
574:
554:
534:
450:
417:
364:
336:
316:
289:
262:
242:
218:
198:
178:
151:
129:is a nonterminal and
124:
101:
29:context-free grammars
2431:Cocke-Kasami-Younger
2332:
2039:
1986:
1941:
1893:
1848:
1808:
1707:
1649:
1573:
1447:
1402:
1356:
1305:
1240:
1195:
1113:
1066:
1008:
977:
880:
769:
717:
665:
583:
563:
543:
491:
457:a nonterminal symbol
433:
376:
369:is defined by the 4-
353:
325:
298:
271:
251:
231:
207:
187:
160:
133:
113:
58:
17:Conjunctive grammars
2474:string homomorphism
1801:, with productions
469:is a finite set of
2623:Artur Jeż (2007).
2488:language equations
2416:Parsing algorithms
2398:
2315:
2018:
1970:
1925:
1877:
1832:
1791:
1685:
1632:
1559:
1433:
1378:
1338:
1291:
1226:
1178:
1099:
1052:
990:
955:
862:language equations
847:
755:
703:
621:
569:
549:
529:
445:
412:
359:
331:
311:
284:
257:
237:
213:
193:
173:
146:
119:
96:
2597:978-3-642-20711-2
2500:pushdown automata
2429:, the cubic-time
2425:, the cubic-time
2423:recursive descent
2014:
2006:
1966:
1958:
1921:
1913:
1873:
1865:
1544:
1543:“)”
1536:
1528:
1520:
1519:“(”
1429:
1424:
1410:
940:
939:“)”
932:
924:
916:
915:“(”
817:
809:
643:s of the grammar.
631:. The members of
572:{\displaystyle V}
552:{\displaystyle A}
473:s, disjoint from
362:{\displaystyle G}
345:Formal definition
334:{\displaystyle A}
240:{\displaystyle w}
216:{\displaystyle V}
122:{\displaystyle A}
2747:
2740:Formal languages
2723:
2702:
2676:
2671:. Archived from
2659:
2657:
2655:
2650:. 9 October 2011
2643:
2641:
2639:
2629:
2610:
2609:
2575:
2569:
2568:
2558:
2549:
2532:
2529:
2523:
2520:
2472:, but not under
2459:context-freeness
2407:
2405:
2404:
2399:
2382:
2381:
2372:
2371:
2362:
2361:
2324:
2322:
2321:
2316:
2027:
2025:
2024:
2019:
2012:
2011:
2004:
1979:
1977:
1976:
1971:
1964:
1963:
1956:
1934:
1932:
1931:
1926:
1919:
1918:
1911:
1886:
1884:
1883:
1878:
1871:
1870:
1863:
1841:
1839:
1838:
1833:
1800:
1798:
1797:
1792:
1694:
1692:
1691:
1686:
1641:
1639:
1638:
1633:
1624:
1623:
1605:
1604:
1592:
1591:
1568:
1566:
1565:
1560:
1558:
1557:
1545:
1542:
1537:
1534:
1529:
1526:
1521:
1518:
1495:
1494:
1476:
1475:
1442:
1440:
1439:
1434:
1427:
1426:
1425:
1423:
1418:
1413:
1408:
1397:
1391:
1387:
1385:
1384:
1379:
1374:
1373:
1347:
1345:
1344:
1339:
1337:
1336:
1324:
1323:
1300:
1298:
1297:
1292:
1290:
1289:
1259:
1258:
1235:
1233:
1232:
1227:
1225:
1224:
1187:
1185:
1184:
1179:
1177:
1176:
1164:
1163:
1145:
1144:
1132:
1131:
1108:
1106:
1105:
1100:
1098:
1097:
1085:
1084:
1061:
1059:
1058:
1053:
1045:
1044:
1026:
1025:
999:
997:
996:
991:
972:
969:directly yields
968:
964:
962:
961:
956:
954:
953:
941:
938:
933:
930:
925:
922:
917:
914:
876:For any strings
856:
854:
853:
848:
846:
845:
827:
826:
815:
814:
807:
806:
805:
787:
786:
764:
762:
761:
756:
754:
753:
735:
734:
712:
710:
709:
704:
702:
701:
683:
682:
652:
648:
634:
630:
628:
627:
622:
620:
619:
595:
594:
578:
576:
575:
570:
558:
556:
555:
550:
538:
536:
535:
530:
528:
527:
509:
508:
486:
480:
476:
468:
454:
452:
451:
446:
428:
421:
419:
418:
413:
368:
366:
365:
360:
340:
338:
337:
332:
320:
318:
317:
312:
310:
309:
293:
291:
290:
285:
283:
282:
266:
264:
263:
258:
246:
244:
243:
238:
223:(finite sets of
222:
220:
219:
214:
202:
200:
199:
194:
182:
180:
179:
174:
172:
171:
155:
153:
152:
147:
145:
144:
128:
126:
125:
120:
105:
103:
102:
97:
95:
94:
76:
75:
42:Boolean grammars
2755:
2754:
2750:
2749:
2748:
2746:
2745:
2744:
2730:
2729:
2705:
2679:
2662:
2653:
2651:
2646:
2637:
2635:
2627:
2622:
2619:
2614:
2613:
2598:
2577:
2576:
2572:
2556:
2551:
2550:
2546:
2541:
2536:
2535:
2530:
2526:
2521:
2517:
2512:
2496:
2443:
2418:
2373:
2363:
2353:
2330:
2329:
2037:
2036:
1984:
1983:
1939:
1938:
1891:
1890:
1846:
1845:
1806:
1805:
1705:
1704:
1701:
1647:
1646:
1615:
1596:
1583:
1571:
1570:
1549:
1486:
1467:
1445:
1444:
1400:
1399:
1395:
1389:
1365:
1354:
1353:
1352:For any string
1328:
1315:
1303:
1302:
1281:
1250:
1238:
1237:
1216:
1193:
1192:
1168:
1155:
1136:
1123:
1111:
1110:
1089:
1076:
1064:
1063:
1036:
1017:
1006:
1005:
975:
974:
970:
966:
945:
878:
877:
874:
837:
818:
797:
778:
767:
766:
745:
726:
715:
714:
693:
674:
663:
662:
650:
646:
635:are called the
632:
611:
586:
581:
580:
561:
560:
541:
540:
519:
500:
489:
488:
484:
478:
474:
466:
431:
430:
426:
374:
373:
351:
350:
347:
323:
322:
301:
296:
295:
274:
269:
268:
249:
248:
229:
228:
205:
204:
185:
184:
163:
158:
157:
136:
131:
130:
111:
110:
86:
67:
56:
55:
25:formal language
21:formal grammars
19:are a class of
12:
11:
5:
2753:
2751:
2743:
2742:
2732:
2731:
2728:
2727:
2714:(3): 597–615.
2703:
2677:
2675:on 2007-09-29.
2660:
2644:
2618:
2617:External links
2615:
2612:
2611:
2596:
2570:
2543:
2542:
2540:
2537:
2534:
2533:
2524:
2514:
2513:
2511:
2508:
2495:
2492:
2442:
2439:
2427:generalized LR
2417:
2414:
2397:
2394:
2391:
2388:
2385:
2380:
2376:
2370:
2366:
2360:
2356:
2352:
2349:
2346:
2343:
2340:
2337:
2326:
2325:
2314:
2311:
2308:
2305:
2302:
2299:
2296:
2293:
2290:
2287:
2284:
2281:
2278:
2275:
2272:
2269:
2266:
2263:
2260:
2257:
2254:
2251:
2248:
2245:
2242:
2239:
2236:
2233:
2230:
2227:
2224:
2221:
2218:
2215:
2212:
2209:
2206:
2203:
2200:
2197:
2194:
2191:
2188:
2185:
2182:
2179:
2176:
2173:
2170:
2167:
2164:
2161:
2158:
2155:
2152:
2149:
2146:
2143:
2140:
2137:
2134:
2131:
2128:
2125:
2122:
2119:
2116:
2113:
2110:
2107:
2104:
2101:
2098:
2095:
2092:
2089:
2086:
2083:
2080:
2077:
2074:
2071:
2068:
2065:
2062:
2059:
2056:
2053:
2050:
2047:
2044:
2030:
2029:
2017:
2010:
2003:
2000:
1997:
1994:
1991:
1981:
1969:
1962:
1955:
1952:
1949:
1946:
1936:
1924:
1917:
1910:
1907:
1904:
1901:
1898:
1888:
1876:
1869:
1862:
1859:
1856:
1853:
1843:
1831:
1828:
1825:
1822:
1819:
1816:
1813:
1790:
1787:
1784:
1781:
1778:
1775:
1772:
1769:
1766:
1763:
1760:
1757:
1754:
1751:
1748:
1745:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1721:
1718:
1715:
1712:
1700:
1697:
1684:
1681:
1678:
1675:
1672:
1669:
1666:
1663:
1660:
1657:
1654:
1631:
1628:
1622:
1618:
1614:
1611:
1608:
1603:
1599:
1595:
1590:
1586:
1581:
1578:
1556:
1552:
1548:
1540:
1532:
1524:
1516:
1513:
1510:
1507:
1504:
1501:
1498:
1493:
1489:
1485:
1482:
1479:
1474:
1470:
1465:
1461:
1458:
1455:
1452:
1432:
1422:
1417:
1407:
1377:
1372:
1368:
1364:
1361:
1350:
1349:
1335:
1331:
1327:
1322:
1318:
1314:
1310:
1288:
1284:
1280:
1277:
1274:
1271:
1268:
1265:
1262:
1257:
1253:
1249:
1245:
1223:
1219:
1215:
1212:
1209:
1206:
1203:
1200:
1189:
1175:
1171:
1167:
1162:
1158:
1154:
1151:
1148:
1143:
1139:
1135:
1130:
1126:
1122:
1118:
1096:
1092:
1088:
1083:
1079:
1075:
1071:
1051:
1048:
1043:
1039:
1035:
1032:
1029:
1024:
1020:
1016:
1013:
988:
985:
982:
952:
948:
944:
936:
928:
920:
912:
909:
906:
903:
900:
897:
894:
891:
888:
885:
873:
870:
844:
840:
836:
833:
830:
825:
821:
813:
804:
800:
796:
793:
790:
785:
781:
777:
774:
752:
748:
744:
741:
738:
733:
729:
725:
722:
700:
696:
692:
689:
686:
681:
677:
673:
670:
655:
654:
644:
618:
614:
610:
607:
604:
601:
598:
593:
589:
568:
548:
526:
522:
518:
515:
512:
507:
503:
499:
496:
482:
464:
444:
441:
438:
411:
408:
405:
402:
399:
396:
393:
390:
387:
384:
381:
358:
346:
343:
330:
308:
304:
281:
277:
256:
236:
212:
192:
170:
166:
143:
139:
118:
107:
106:
93:
89:
85:
82:
79:
74:
70:
66:
63:
13:
10:
9:
6:
4:
3:
2:
2752:
2741:
2738:
2737:
2735:
2726:
2721:
2717:
2713:
2709:
2704:
2701:
2697:
2693:
2689:
2685:
2684:
2678:
2674:
2670:
2666:
2661:
2649:
2645:
2633:
2626:
2621:
2620:
2616:
2607:
2603:
2599:
2593:
2589:
2585:
2581:
2574:
2571:
2567:(4): 519–535.
2566:
2562:
2555:
2548:
2545:
2538:
2528:
2525:
2519:
2516:
2509:
2507:
2505:
2502:(PDA) called
2501:
2493:
2491:
2489:
2484:
2481:
2479:
2475:
2471:
2467:
2466:concatenation
2462:
2460:
2456:
2452:
2448:
2440:
2438:
2436:
2433:, as well as
2432:
2428:
2424:
2415:
2413:
2411:
2392:
2389:
2386:
2383:
2378:
2374:
2368:
2364:
2358:
2354:
2347:
2341:
2335:
2312:
2309:
2306:
2297:
2294:
2291:
2285:
2282:
2279:
2267:
2264:
2261:
2258:
2252:
2249:
2246:
2234:
2231:
2228:
2222:
2219:
2216:
2204:
2201:
2198:
2195:
2189:
2186:
2183:
2171:
2168:
2162:
2159:
2156:
2144:
2141:
2135:
2132:
2129:
2126:
2114:
2111:
2105:
2102:
2090:
2087:
2081:
2078:
2075:
2063:
2060:
2054:
2051:
2042:
2035:
2034:
2033:
2015:
2001:
1998:
1995:
1989:
1982:
1967:
1953:
1950:
1944:
1937:
1922:
1908:
1905:
1902:
1896:
1889:
1874:
1860:
1857:
1851:
1844:
1829:
1826:
1820:
1817:
1811:
1804:
1803:
1802:
1785:
1782:
1779:
1776:
1770:
1767:
1764:
1761:
1758:
1752:
1746:
1743:
1740:
1737:
1734:
1731:
1728:
1725:
1722:
1713:
1710:
1698:
1696:
1679:
1676:
1673:
1670:
1664:
1661:
1655:
1652:
1643:
1629:
1626:
1620:
1616:
1609:
1601:
1597:
1588:
1584:
1579:
1576:
1554:
1538:
1522:
1511:
1505:
1502:
1496:
1491:
1487:
1483:
1480:
1477:
1472:
1468:
1459:
1456:
1453:
1430:
1420:
1405:
1398:, written as
1394:
1375:
1370:
1362:
1359:
1333:
1329:
1325:
1320:
1316:
1312:
1308:
1286:
1282:
1275:
1269:
1263:
1255:
1251:
1247:
1243:
1221:
1210:
1207:
1201:
1198:
1190:
1173:
1169:
1160:
1156:
1149:
1141:
1137:
1128:
1124:
1120:
1116:
1094:
1090:
1086:
1081:
1077:
1073:
1069:
1049:
1046:
1041:
1037:
1030:
1022:
1018:
1011:
1003:
1002:
1001:
986:
980:
973:, written as
950:
934:
918:
907:
901:
898:
892:
889:
886:
883:
871:
869:
867:
863:
858:
842:
838:
831:
823:
819:
802:
798:
791:
783:
779:
772:
750:
746:
739:
731:
727:
720:
698:
694:
687:
679:
675:
668:
660:
645:
642:
638:
616:
605:
602:
596:
591:
587:
566:
546:
524:
520:
513:
505:
501:
494:
483:
472:
465:
462:
458:
442:
439:
436:
425:
424:
423:
406:
403:
400:
397:
391:
388:
382:
379:
372:
356:
344:
342:
328:
306:
302:
279:
275:
234:
226:
210:
168:
164:
141:
137:
116:
91:
87:
80:
72:
68:
61:
54:
53:
52:
49:
47:
43:
38:
34:
30:
26:
22:
18:
2711:
2707:
2699:
2687:
2681:
2673:the original
2668:
2652:. Retrieved
2636:. Retrieved
2579:
2573:
2564:
2560:
2547:
2527:
2518:
2497:
2485:
2482:
2463:
2444:
2419:
2327:
2031:
1703:The grammar
1702:
1644:
1392:
1351:
875:
859:
656:
640:
636:
470:
460:
456:
348:
108:
50:
16:
15:
2470:Kleene star
659:pipe symbol
37:disjunction
33:conjunction
23:studied in
2654:5 November
2638:5 November
2539:References
2455:regularity
2451:finiteness
1569:such that
1236:such that
1062:such that
641:production
455:is called
2690:: 27–59.
2606:0302-9743
2447:emptiness
2435:Valiant's
2390:≥
2304:⇒
2289:&
2274:⇒
2256:&
2241:⇒
2226:&
2211:⇒
2193:&
2178:⇒
2166:&
2151:⇒
2139:&
2121:⇒
2109:&
2097:⇒
2085:&
2070:⇒
2058:&
2046:⇒
2016:ϵ
1993:→
1968:ϵ
1948:→
1923:ϵ
1900:→
1875:ϵ
1855:→
1824:&
1815:→
1668:Σ
1613:⇒
1610:⋯
1607:⇒
1594:⇒
1555:∗
1531:&
1512:∪
1509:Σ
1506:∪
1497:∈
1481:⋯
1464:∃
1457:≥
1451:∃
1421:∗
1416:⇒
1393:generates
1371:∗
1367:Σ
1363:∈
1273:&
1270:…
1267:&
1222:∗
1214:Σ
1211:∪
1202:∈
1157:α
1153:&
1150:…
1147:&
1138:α
1047:∈
1038:α
1034:&
1031:…
1028:&
1019:α
1015:→
984:⇒
965:, we say
951:∗
927:&
908:∪
905:Σ
902:∪
893:∈
866:Chomsky's
839:β
835:&
832:…
829:&
820:β
799:α
795:&
792:…
789:&
780:α
776:→
747:β
743:&
740:…
737:&
728:β
724:→
695:α
691:&
688:…
685:&
676:α
672:→
617:∗
609:Σ
606:∪
597:∈
588:α
539:for some
521:α
517:&
514:…
511:&
502:α
498:→
440:∈
395:Σ
303:α
276:α
255:Σ
191:Σ
165:α
138:α
88:α
84:&
81:…
78:&
69:α
65:→
31:, with a
2734:Category
1535:”
1527:“
931:”
923:“
471:terminal
461:variable
46:negation
1699:Example
1388:we say
294:, ...,
156:, ...,
2604:
2594:
2478:prefix
2013:
2005:
1965:
1957:
1920:
1912:
1872:
1864:
1428:
1409:
1000:, if
816:
808:
467:Σ
422:where
109:where
2628:(PDF)
2557:(PDF)
2510:Notes
1443:, if
639:s or
459:or a
371:tuple
247:over
2656:2019
2640:2019
2602:ISSN
2592:ISBN
2468:and
1301:and
1109:and
713:and
637:rule
579:and
203:and
2716:doi
2692:doi
2584:doi
559:in
2736::
2712:19
2710:.
2698:.
2686:.
2667:.
2600:.
2590:.
2563:.
2559:.
2476:,
2457:,
2453:,
2449:,
2412:.
1642:.
857:.
341:.
48:.
2722:.
2718::
2694::
2688:9
2658:.
2642:.
2634:)
2608:.
2586::
2565:6
2396:}
2393:0
2387:n
2384::
2379:n
2375:c
2369:n
2365:b
2359:n
2355:a
2351:{
2348:=
2345:)
2342:G
2339:(
2336:L
2313:c
2310:b
2307:a
2301:)
2298:c
2295:b
2292:a
2286:c
2283:b
2280:a
2277:(
2271:)
2268:C
2265:c
2262:b
2259:a
2253:c
2250:b
2247:a
2244:(
2238:)
2235:C
2232:b
2229:a
2223:c
2220:b
2217:a
2214:(
2208:)
2205:C
2202:b
2199:D
2196:a
2190:c
2187:b
2184:a
2181:(
2175:)
2172:C
2169:D
2163:c
2160:b
2157:a
2154:(
2148:)
2145:C
2142:D
2136:c
2133:B
2130:b
2127:a
2124:(
2118:)
2115:C
2112:D
2106:B
2103:a
2100:(
2094:)
2091:C
2088:D
2082:B
2079:A
2076:a
2073:(
2067:)
2064:C
2061:D
2055:B
2052:A
2049:(
2043:S
2028:,
2009:|
2002:b
1999:D
1996:a
1990:D
1980:,
1961:|
1954:C
1951:c
1945:C
1935:,
1916:|
1909:c
1906:B
1903:b
1897:B
1887:,
1868:|
1861:A
1858:a
1852:A
1842:,
1830:C
1827:D
1821:B
1818:A
1812:S
1789:)
1786:S
1783:,
1780:R
1777:,
1774:}
1771:c
1768:,
1765:b
1762:,
1759:a
1756:{
1753:,
1750:}
1747:D
1744:,
1741:C
1738:,
1735:B
1732:,
1729:A
1726:,
1723:S
1720:{
1717:(
1714:=
1711:G
1683:)
1680:S
1677:,
1674:R
1671:,
1665:,
1662:V
1659:(
1656:=
1653:G
1630:w
1627:=
1621:k
1617:u
1602:2
1598:u
1589:1
1585:u
1580:=
1577:S
1551:)
1547:}
1539:,
1523:,
1515:{
1503:V
1500:(
1492:k
1488:u
1484:,
1478:,
1473:1
1469:u
1460:1
1454:k
1431:w
1406:S
1396:w
1390:G
1376:,
1360:w
1348:.
1334:2
1330:u
1326:w
1321:1
1317:u
1313:=
1309:v
1287:2
1283:u
1279:)
1276:w
1264:w
1261:(
1256:1
1252:u
1248:=
1244:u
1218:)
1208:V
1205:(
1199:w
1188:,
1174:2
1170:u
1166:)
1161:m
1142:1
1134:(
1129:1
1125:u
1121:=
1117:v
1095:2
1091:u
1087:A
1082:1
1078:u
1074:=
1070:u
1050:R
1042:m
1023:1
1012:A
987:v
981:u
971:v
967:u
947:)
943:}
935:,
919:,
911:{
899:V
896:(
890:v
887:,
884:u
843:n
824:1
812:|
803:m
784:1
773:A
751:n
732:1
721:A
699:m
680:1
669:A
653:.
651:V
647:S
633:R
613:)
603:V
600:(
592:i
567:V
547:A
525:m
506:1
495:A
485:R
481:.
479:G
475:V
443:V
437:v
427:V
410:)
407:S
404:,
401:R
398:,
392:,
389:V
386:(
383:=
380:G
357:G
329:A
307:m
280:1
235:w
211:V
169:m
142:1
117:A
92:m
73:1
62:A
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.