20:
1026:
1197:
324:
1618:
1336:
726:
539:
235:
1085:
1080:
893:
622:
1075:
851:
1524:
1232:
768:
664:
1384:
887:
423:
1256:
1628:
When a language is given by a regular expression, the concept of derivatives leads to an algorithm for deciding whether a given word belongs to the regular expression.
1491:
390:
69:
1414:
247:
1458:
1438:
1276:
566:
463:
443:
370:
159:
136:
116:
92:
2022:
Using the previous two rules, the derivative with respect to an arbitrary string is explained by the derivative with respect to a single-symbol string
1532:
330:
329:
The
Brzozowski derivative was introduced under various different names since the late 1950s. Today it is named after the computer scientist
2519:
Derivatives are also effectively computable for recursively defined equations with regular expression operators, which are equivalent to
1284:
2885:
1032:
The derivative with respect to an arbitrary string reduces to successive derivatives over the symbols of that string, since for all
672:
471:
167:
2860:. Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI). pp. 224–236.
2856:
Michael D. Adams; Celeste
Hollenbeck; Matthew Might (2016). "On the complexity and performance of parsing with derivatives".
2491:
2548:
545:
1021:{\displaystyle w\in (uv)^{-1}S\Leftrightarrow uvw\in S\Leftrightarrow vw\in u^{-1}S\Leftrightarrow w\in v^{-1}(u^{-1}S)}
349:
Even though originally studied for regular expressions, the definition applies to arbitrary formal languages. Given any
28:
571:
1035:
2837:. Proceeding of the 16th ACM SIGPLAN international conference on Functional Programming (ICFP). pp. 189–195.
2508:
2907:
139:
776:
1496:
1350:
1204:
95:
1342:
32:
2528:
1192:{\displaystyle {\begin{aligned}(ua)^{-1}S&=a^{-1}(u^{-1}S)\\\varepsilon ^{-1}S&=S\end{aligned}}}
734:
630:
2254:
is an auxiliary function yielding a generalized regular expression that evaluates to the empty string
1356:
859:
395:
2648:
C.C. Elgot and J.D. Rutledge (Oct 1961). "Operations on finite automata". In Robert S. Ledley (ed.).
2520:
23:
Brzozowski derivative (on red background) of a dictionary string set with respect to the string "con"
1241:
2861:
2737:
2696:
2589:
338:
2858:
Proceedings of the 37th ACM SIGPLAN Conference on
Programming Language Design and Implementation
2881:
1346:
72:
1463:
375:
319:{\displaystyle c^{-1}\{{\text{cat}},{\text{cow}},{\text{dog}}\}=\{{\text{at}},{\text{ow}}\}.}
41:
2871:
2838:
2727:
2686:
2655:
2630:
2581:
1393:
2651:
Proc. AIEE 2nd Ann. Symp. on
Switching, Circuit Theory, and Logical Design (SWCT), Detroit
2532:
350:
1902:
1443:
1423:
1261:
551:
448:
428:
355:
144:
121:
101:
77:
2615:
2266:, and otherwise evaluates to ∅. This function can be computed by the following rules:
19:
2901:
2611:
2536:
2741:
2700:
2593:
2468:
results in only finitely many different languages. If their number is denoted by
1613:{\displaystyle S=(\{\varepsilon \}\cap S)\cup \bigcup _{a\in \Sigma }a(a^{-1}S).}
2649:
2569:
2607:
2876:
2842:
1420:
otherwise. In this interpretation, the derivative with respect to a symbol
334:
1645:
denotes a possibly infinite set of finite-length strings over the alphabet
2732:
2715:
2691:
2674:
2585:
2464:
Considering all the derivatives of a fixed generalized regular expression
2450:
is a member of the string set denoted by a generalized regular expression
2659:
2454:
if and only if ε is a member of the string set denoted by the derivative
1632:
2634:
2524:
1493:
corresponds to the following equality, which holds for every language
1341:
A language can be viewed as a (potentially infinite) boolean-labelled
1668:
A generalized regular expression can be one of the following (where
2866:
1952:
is again a generalized regular expression (denoting the language
1460:
from the root. Decomposing a tree into the root and the subtrees
1331:{\displaystyle w\in S\ \Leftrightarrow \ \varepsilon \in w^{-1}S}
1706:" denotes the singleton set containing the single-symbol string
1929:
In an ordinary regular expression, neither ∧ nor ¬ is allowed.
2762:
2531:. Implementation of such algorithms have shown to have cubic
607:
1695:"ε" denotes the singleton set containing the empty string:
1440:
corresponds to the subtree obtained by following the edge
1278:
is uniquely determined by nullability of its derivatives:
2477:, all these languages can be obtained as derivatives of
721:{\displaystyle v\in u^{-1}S\;\Leftrightarrow \;uv\in S.}
534:{\displaystyle u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}}
230:{\displaystyle u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}}
16:
Function defined on formal languages in computer science
118:
is the set of all strings obtainable from a string in
2503:
states that recognises the regular language given by
1535:
1499:
1466:
1446:
1426:
1396:
1359:
1287:
1264:
1244:
1207:
1083:
1038:
896:
862:
779:
737:
675:
633:
574:
554:
474:
451:
431:
398:
378:
358:
250:
170:
147:
124:
104:
80:
44:
2833:
Matthew Might; David Darais; Daniel
Spiewak (2011).
1612:
1518:
1485:
1452:
1432:
1408:
1378:
1330:
1270:
1250:
1226:
1191:
1069:
1020:
881:
845:
762:
720:
658:
616:
560:
533:
457:
437:
417:
384:
364:
318:
229:
153:
130:
110:
86:
63:
1963:)). It may be computed recursively as follows.
617:{\displaystyle \ u^{-1}S=\{u\}\;\backslash \;S}
544:The Brzozowski derivative is a special case of
1624:Derivatives of generalized regular expressions
2616:"Finite Automata and Their Decision Problems"
1937:For any given generalized regular expression
1070:{\displaystyle a\in \Sigma ,u\in \Sigma ^{*}}
8:
2835:Parsing with derivatives: a functional pearl
2481:with respect to strings of length less than
1551:
1545:
1238:if and only if it contains the empty string
603:
597:
528:
494:
333:who investigated its properties and gave an
310:
294:
288:
264:
224:
190:
337:to compute the derivative of a generalized
846:{\displaystyle (uv)^{-1}S=v^{-1}(u^{-1}S)}
702:
698:
610:
606:
2875:
2865:
2731:
2690:
2535:, corresponding to the complexity of the
2026:. The latter can be computed as follows:
1592:
1570:
1534:
1510:
1498:
1471:
1465:
1445:
1425:
1395:
1370:
1358:
1316:
1286:
1263:
1243:
1218:
1206:
1163:
1140:
1124:
1101:
1084:
1082:
1061:
1037:
1003:
987:
962:
916:
895:
873:
861:
828:
812:
793:
778:
754:
736:
686:
674:
650:
632:
582:
573:
553:
507:
479:
473:
450:
430:
409:
397:
377:
357:
305:
297:
283:
275:
267:
255:
249:
203:
175:
169:
146:
123:
103:
79:
49:
43:
2805:Brzozowski (1964), p.482, Definition 3.2
18:
2623:IBM Journal of Research and Development
2560:
1386:denotes a node in the tree, with label
1684:are generalized regular expressions):
1519:{\displaystyle S\subseteq \Sigma ^{*}}
1227:{\displaystyle S\subseteq \Sigma ^{*}}
2823:Brzozowski (1964), p.484, Theorem 4.3
2814:Brzozowski (1964), p.483, Theorem 4.2
2796:Brzozowski (1964), p.483, Theorem 3.1
2787:Brzozowski (1964), p.483, Theorem 3.2
2778:Brzozowski (1964), p.483, Theorem 4.1
2515:Derivatives of context-free languages
7:
2758:to consist of the 2 combinations of
2716:"Derivatives of Regular Expressions"
2675:"Derivatives of Regular Expressions"
2754:Brzozowski (1964), p.481, required
2490:. Furthermore, there is a complete
548:by a singleton set containing only
2539:on general context-free grammars.
2523:. This insight was used to derive
1993: for a symbol
1577:
1507:
1367:
1215:
1058:
1045:
870:
763:{\displaystyle u,v\in \Sigma ^{*}}
751:
659:{\displaystyle u,v\in \Sigma ^{*}}
647:
504:
406:
379:
200:
14:
1379:{\displaystyle w\in \Sigma ^{*}}
882:{\displaystyle w\in \Sigma ^{*}}
418:{\displaystyle u\in \Sigma ^{*}}
1862:" denotes the concatenation of
1831:*, the set of all strings over
2492:deterministic finite automaton
1780:" denotes the intersection of
1640:generalized regular expression
1604:
1585:
1560:
1542:
1300:
1152:
1133:
1098:
1088:
1015:
996:
974:
946:
928:
913:
903:
840:
821:
790:
780:
699:
1:
2714:Janusz A. Brzozowski (1964).
2673:Janusz A. Brzozowski (1964).
2549:Quotient of a formal language
731:From the definition, for all
2568:George N. Raney (Apr 1958).
1823:" denotes the complement of
1672:is a symbol of the alphabet
1251:{\displaystyle \varepsilon }
29:theoretical computer science
1688:"∅" denotes the empty set:
2924:
1353:). Each possible string
2877:10.1145/2908080.2908128
2843:10.1145/2034773.2034801
1733:" denotes the union of
1486:{\displaystyle a^{-1}S}
1351:infinite-tree automaton
385:{\displaystyle \Sigma }
64:{\displaystyle u^{-1}S}
2570:"Sequential functions"
2529:context-free languages
1614:
1520:
1487:
1454:
1434:
1410:
1409:{\displaystyle w\in S}
1380:
1332:
1272:
1252:
1228:
1193:
1071:
1022:
883:
847:
764:
722:
660:
627:Equivalently, for all
618:
562:
535:
459:
439:
419:
386:
366:
320:
231:
155:
132:
112:
88:
65:
33:formal language theory
24:
2733:10.1145/321239.321249
2692:10.1145/321239.321249
2586:10.1145/320924.320930
2521:context-free grammars
2509:Myhill–Nerode theorem
2262:'s language contains
1615:
1521:
1488:
1455:
1435:
1411:
1381:
1333:
1273:
1253:
1229:
1194:
1072:
1023:
884:
848:
765:
723:
661:
619:
563:
536:
460:
440:
420:
387:
367:
321:
232:
156:
133:
113:
89:
66:
37:Brzozowski derivative
22:
2660:10.1109/FOCS.1961.26
2654:. pp. 129–132.
1533:
1497:
1464:
1444:
1424:
1394:
1357:
1285:
1262:
1242:
1205:
1081:
1036:
894:
860:
777:
735:
673:
631:
572:
552:
472:
449:
429:
425:, the derivative of
396:
376:
356:
248:
168:
145:
122:
102:
78:
42:
2507:, as stated by the
138:by cutting off the
31:, in particular in
2635:10.1147/rd.32.0114
2574:Journal of the ACM
1610:
1581:
1516:
1483:
1450:
1430:
1406:
1376:
1328:
1268:
1248:
1224:
1189:
1187:
1067:
1018:
879:
843:
760:
718:
656:
614:
558:
531:
455:
435:
415:
382:
362:
339:regular expression
316:
227:
151:
128:
108:
84:
61:
25:
2439:
2438:
2244:
2243:
2020:
2019:
1945:, the derivative
1827:(with respect to
1566:
1453:{\displaystyle a}
1433:{\displaystyle a}
1347:tree (set theory)
1305:
1299:
1271:{\displaystyle S}
577:
561:{\displaystyle u}
458:{\displaystyle u}
438:{\displaystyle S}
372:over an alphabet
365:{\displaystyle S}
331:Janusz Brzozowski
308:
300:
286:
278:
270:
154:{\displaystyle u}
131:{\displaystyle S}
111:{\displaystyle u}
87:{\displaystyle S}
2915:
2908:Formal languages
2892:
2891:
2879:
2869:
2853:
2847:
2846:
2830:
2824:
2821:
2815:
2812:
2806:
2803:
2797:
2794:
2788:
2785:
2779:
2776:
2770:
2752:
2746:
2745:
2735:
2711:
2705:
2704:
2694:
2670:
2664:
2663:
2645:
2639:
2638:
2620:
2604:
2598:
2597:
2565:
2269:
2268:
2253:
2059:for each symbol
2029:
2028:
1966:
1965:
1619:
1617:
1616:
1611:
1600:
1599:
1580:
1525:
1523:
1522:
1517:
1515:
1514:
1492:
1490:
1489:
1484:
1479:
1478:
1459:
1457:
1456:
1451:
1439:
1437:
1436:
1431:
1415:
1413:
1412:
1407:
1385:
1383:
1382:
1377:
1375:
1374:
1337:
1335:
1334:
1329:
1324:
1323:
1303:
1297:
1277:
1275:
1274:
1269:
1258:. Each language
1257:
1255:
1254:
1249:
1233:
1231:
1230:
1225:
1223:
1222:
1198:
1196:
1195:
1190:
1188:
1171:
1170:
1148:
1147:
1132:
1131:
1109:
1108:
1076:
1074:
1073:
1068:
1066:
1065:
1029:
1027:
1025:
1024:
1019:
1011:
1010:
995:
994:
970:
969:
924:
923:
888:
886:
885:
880:
878:
877:
852:
850:
849:
844:
836:
835:
820:
819:
801:
800:
769:
767:
766:
761:
759:
758:
727:
725:
724:
719:
694:
693:
665:
663:
662:
657:
655:
654:
623:
621:
620:
615:
590:
589:
575:
567:
565:
564:
559:
540:
538:
537:
532:
512:
511:
487:
486:
464:
462:
461:
456:
445:with respect to
444:
442:
441:
436:
424:
422:
421:
416:
414:
413:
391:
389:
388:
383:
371:
369:
368:
363:
325:
323:
322:
317:
309:
306:
301:
298:
287:
284:
279:
276:
271:
268:
263:
262:
236:
234:
233:
228:
208:
207:
183:
182:
160:
158:
157:
152:
137:
135:
134:
129:
117:
115:
114:
109:
93:
91:
90:
85:
70:
68:
67:
62:
57:
56:
2923:
2922:
2918:
2917:
2916:
2914:
2913:
2912:
2898:
2897:
2896:
2895:
2888:
2855:
2854:
2850:
2832:
2831:
2827:
2822:
2818:
2813:
2809:
2804:
2800:
2795:
2791:
2786:
2782:
2777:
2773:
2753:
2749:
2713:
2712:
2708:
2672:
2671:
2667:
2647:
2646:
2642:
2618:
2606:
2605:
2601:
2567:
2566:
2562:
2557:
2545:
2533:time complexity
2527:algorithms for
2517:
2502:
2489:
2476:
2444:
2282:for any symbol
2247:
1941:and any string
1935:
1901:*" denotes the
1631:Given a finite
1626:
1588:
1531:
1530:
1506:
1495:
1494:
1467:
1462:
1461:
1442:
1441:
1422:
1421:
1392:
1391:
1366:
1355:
1354:
1312:
1283:
1282:
1260:
1259:
1240:
1239:
1214:
1203:
1202:
1186:
1185:
1175:
1159:
1156:
1155:
1136:
1120:
1113:
1097:
1079:
1078:
1057:
1034:
1033:
999:
983:
958:
912:
892:
891:
890:
869:
858:
857:
824:
808:
789:
775:
774:
750:
733:
732:
682:
671:
670:
646:
629:
628:
578:
570:
569:
550:
549:
503:
475:
470:
469:
465:is defined as:
447:
446:
427:
426:
405:
394:
393:
392:and any string
374:
373:
354:
353:
351:formal language
347:
251:
246:
245:
199:
171:
166:
165:
143:
142:
120:
119:
100:
99:
76:
75:
45:
40:
39:
17:
12:
11:
5:
2921:
2919:
2911:
2910:
2900:
2899:
2894:
2893:
2886:
2848:
2825:
2816:
2807:
2798:
2789:
2780:
2771:
2747:
2726:(4): 481–494.
2706:
2685:(4): 481–494.
2665:
2640:
2629:(2): 114–125.
2599:
2580:(2): 177–180.
2559:
2558:
2556:
2553:
2552:
2551:
2544:
2541:
2516:
2513:
2498:
2485:
2472:
2443:
2440:
2437:
2436:
2426:
2423:
2415:
2414:
2407:
2401:
2393:
2392:
2381:
2369:
2368:
2357:
2345:
2344:
2333:
2325:
2324:
2318:
2310:
2309:
2306:
2302:
2301:
2295:
2287:
2286:
2280:
2277:
2242:
2241:
2231:
2220:
2219:
2202:
2187:
2186:
2169:
2154:
2153:
2129:
2118:
2117:
2103:
2092:
2091:
2088:
2081:
2080:
2077:
2068:
2067:
2057:
2054:
2045:
2044:
2038:
2018:
2017:
2011:
2002:
2001:
1991:
1977:
1934:
1931:
1927:
1926:
1903:Kleene closure
1895:
1856:
1817:
1770:
1723:
1700:
1693:
1638:of symbols, a
1625:
1622:
1621:
1620:
1609:
1606:
1603:
1598:
1595:
1591:
1587:
1584:
1579:
1576:
1573:
1569:
1565:
1562:
1559:
1556:
1553:
1550:
1547:
1544:
1541:
1538:
1513:
1509:
1505:
1502:
1482:
1477:
1474:
1470:
1449:
1429:
1405:
1402:
1399:
1373:
1369:
1365:
1362:
1339:
1338:
1327:
1322:
1319:
1315:
1311:
1308:
1302:
1296:
1293:
1290:
1267:
1247:
1221:
1217:
1213:
1210:
1184:
1181:
1178:
1176:
1174:
1169:
1166:
1162:
1158:
1157:
1154:
1151:
1146:
1143:
1139:
1135:
1130:
1127:
1123:
1119:
1116:
1114:
1112:
1107:
1104:
1100:
1096:
1093:
1090:
1087:
1086:
1064:
1060:
1056:
1053:
1050:
1047:
1044:
1041:
1017:
1014:
1009:
1006:
1002:
998:
993:
990:
986:
982:
979:
976:
973:
968:
965:
961:
957:
954:
951:
948:
945:
942:
939:
936:
933:
930:
927:
922:
919:
915:
911:
908:
905:
902:
899:
876:
872:
868:
865:
856:since for all
854:
853:
842:
839:
834:
831:
827:
823:
818:
815:
811:
807:
804:
799:
796:
792:
788:
785:
782:
757:
753:
749:
746:
743:
740:
729:
728:
717:
714:
711:
708:
705:
701:
697:
692:
689:
685:
681:
678:
653:
649:
645:
642:
639:
636:
613:
609:
605:
602:
599:
596:
593:
588:
585:
581:
557:
542:
541:
530:
527:
524:
521:
518:
515:
510:
506:
502:
499:
496:
493:
490:
485:
482:
478:
454:
434:
412:
408:
404:
401:
381:
361:
346:
343:
327:
326:
315:
312:
304:
296:
293:
290:
282:
274:
266:
261:
258:
254:
239:
238:
226:
223:
220:
217:
214:
211:
206:
202:
198:
195:
192:
189:
186:
181:
178:
174:
150:
127:
107:
83:
60:
55:
52:
48:
15:
13:
10:
9:
6:
4:
3:
2:
2920:
2909:
2906:
2905:
2903:
2889:
2887:9781450342612
2883:
2878:
2873:
2868:
2863:
2859:
2852:
2849:
2844:
2840:
2836:
2829:
2826:
2820:
2817:
2811:
2808:
2802:
2799:
2793:
2790:
2784:
2781:
2775:
2772:
2768:
2764:
2761:
2757:
2751:
2748:
2743:
2739:
2734:
2729:
2725:
2721:
2717:
2710:
2707:
2702:
2698:
2693:
2688:
2684:
2680:
2676:
2669:
2666:
2661:
2657:
2653:
2652:
2644:
2641:
2636:
2632:
2628:
2624:
2617:
2613:
2612:Michael Rabin
2609:
2603:
2600:
2595:
2591:
2587:
2583:
2579:
2575:
2571:
2564:
2561:
2554:
2550:
2547:
2546:
2542:
2540:
2538:
2537:Earley parser
2534:
2530:
2526:
2522:
2514:
2512:
2510:
2506:
2501:
2497:
2493:
2488:
2484:
2480:
2475:
2471:
2467:
2462:
2460:
2457:
2453:
2449:
2441:
2435:
2431:
2427:
2424:
2421:
2417:
2416:
2412:
2408:
2406:
2402:
2399:
2395:
2394:
2390:
2386:
2382:
2379:
2375:
2371:
2370:
2366:
2362:
2358:
2355:
2351:
2347:
2346:
2342:
2338:
2334:
2331:
2327:
2326:
2323:
2319:
2316:
2312:
2311:
2307:
2304:
2303:
2300:
2296:
2293:
2289:
2288:
2285:
2281:
2278:
2275:
2271:
2270:
2267:
2265:
2261:
2257:
2251:
2239:
2236:
2232:
2229:
2225:
2222:
2221:
2217:
2214:
2210:
2207:
2203:
2200:
2196:
2192:
2189:
2188:
2184:
2181:
2177:
2174:
2170:
2167:
2163:
2159:
2156:
2155:
2152:
2149:
2145:
2141:
2137:
2134:
2130:
2127:
2123:
2120:
2119:
2115:
2111:
2108:
2104:
2101:
2097:
2094:
2093:
2089:
2086:
2083:
2082:
2078:
2076:
2073:
2070:
2069:
2066:
2062:
2058:
2055:
2053:
2050:
2047:
2046:
2043:
2039:
2037:
2034:
2031:
2030:
2027:
2025:
2016:
2012:
2010:
2007:
2004:
2003:
2000:
1997:and a string
1996:
1992:
1989:
1986:
1982:
1978:
1976:
1972:
1968:
1967:
1964:
1962:
1958:
1955:
1951:
1948:
1944:
1940:
1932:
1930:
1924:
1920:
1916:
1912:
1908:
1904:
1900:
1896:
1893:
1889:
1885:
1881:
1877:
1873:
1869:
1865:
1861:
1857:
1854:
1850:
1846:
1842:
1838:
1834:
1830:
1826:
1822:
1818:
1815:
1811:
1807:
1803:
1799:
1795:
1791:
1787:
1783:
1779:
1775:
1771:
1768:
1764:
1760:
1756:
1752:
1748:
1744:
1740:
1736:
1732:
1728:
1724:
1721:
1717:
1713:
1709:
1705:
1701:
1698:
1694:
1691:
1687:
1686:
1685:
1683:
1679:
1675:
1671:
1666:
1664:
1660:
1656:
1652:
1649:, called the
1648:
1644:
1641:
1637:
1634:
1629:
1623:
1607:
1601:
1596:
1593:
1589:
1582:
1574:
1571:
1567:
1563:
1557:
1554:
1548:
1539:
1536:
1529:
1528:
1527:
1511:
1503:
1500:
1480:
1475:
1472:
1468:
1447:
1427:
1419:
1403:
1400:
1397:
1389:
1371:
1363:
1360:
1352:
1348:
1344:
1325:
1320:
1317:
1313:
1309:
1306:
1294:
1291:
1288:
1281:
1280:
1279:
1265:
1245:
1237:
1219:
1211:
1208:
1199:
1182:
1179:
1177:
1172:
1167:
1164:
1160:
1149:
1144:
1141:
1137:
1128:
1125:
1121:
1117:
1115:
1110:
1105:
1102:
1094:
1091:
1062:
1054:
1051:
1048:
1042:
1039:
1030:
1012:
1007:
1004:
1000:
991:
988:
984:
980:
977:
971:
966:
963:
959:
955:
952:
949:
943:
940:
937:
934:
931:
925:
920:
917:
909:
906:
900:
897:
874:
866:
863:
837:
832:
829:
825:
816:
813:
809:
805:
802:
797:
794:
786:
783:
773:
772:
771:
755:
747:
744:
741:
738:
715:
712:
709:
706:
703:
695:
690:
687:
683:
679:
676:
669:
668:
667:
651:
643:
640:
637:
634:
625:
611:
600:
594:
591:
586:
583:
579:
555:
547:
546:left quotient
525:
522:
519:
516:
513:
508:
500:
497:
491:
488:
483:
480:
476:
468:
467:
466:
452:
432:
410:
402:
399:
359:
352:
344:
342:
340:
336:
332:
313:
302:
291:
280:
272:
259:
256:
252:
244:
243:
242:
241:For example,
221:
218:
215:
212:
209:
204:
196:
193:
187:
184:
179:
176:
172:
164:
163:
162:
148:
141:
125:
105:
98:and a string
97:
81:
74:
58:
53:
50:
46:
38:
34:
30:
21:
2857:
2851:
2834:
2828:
2819:
2810:
2801:
2792:
2783:
2774:
2766:
2759:
2755:
2750:
2723:
2719:
2709:
2682:
2678:
2668:
2650:
2643:
2626:
2622:
2614:(Apr 1959).
2602:
2577:
2573:
2563:
2518:
2504:
2499:
2495:
2486:
2482:
2478:
2473:
2469:
2465:
2463:
2458:
2455:
2451:
2447:
2445:
2433:
2429:
2419:
2410:
2404:
2397:
2388:
2384:
2377:
2373:
2364:
2360:
2353:
2349:
2340:
2336:
2329:
2321:
2314:
2298:
2291:
2283:
2273:
2263:
2259:
2255:
2249:
2245:
2237:
2234:
2227:
2223:
2215:
2212:
2208:
2205:
2198:
2194:
2190:
2182:
2179:
2175:
2172:
2165:
2161:
2157:
2150:
2147:
2143:
2139:
2135:
2132:
2125:
2121:
2113:
2109:
2106:
2099:
2095:
2084:
2074:
2071:
2064:
2060:
2051:
2048:
2041:
2035:
2032:
2023:
2021:
2014:
2008:
2005:
1998:
1994:
1987:
1984:
1980:
1974:
1970:
1960:
1956:
1953:
1949:
1946:
1942:
1938:
1936:
1928:
1922:
1918:
1914:
1910:
1906:
1898:
1891:
1887:
1883:
1879:
1875:
1871:
1867:
1863:
1859:
1852:
1848:
1844:
1840:
1836:
1832:
1828:
1824:
1820:
1813:
1809:
1805:
1801:
1797:
1793:
1789:
1785:
1781:
1777:
1773:
1766:
1762:
1758:
1754:
1750:
1746:
1742:
1738:
1734:
1730:
1726:
1719:
1715:
1711:
1707:
1703:
1696:
1689:
1681:
1677:
1673:
1669:
1667:
1662:
1658:
1654:
1650:
1646:
1642:
1639:
1635:
1630:
1627:
1417:
1387:
1340:
1235:
1200:
1031:
855:
730:
626:
543:
348:
328:
240:
161:. Formally:
36:
26:
2765:, for some
1933:Computation
1201:A language
2867:1604.04695
2608:Dana Scott
2555:References
2442:Properties
1699:(ε) = {ε},
1657:, denoted
1345:(see also
1234:is called
889:, we have
345:Definition
2446:A string
1692:(∅) = {},
1594:−
1578:Σ
1575:∈
1568:⋃
1564:∪
1555:∩
1549:ε
1512:∗
1508:Σ
1504:⊆
1473:−
1401:∈
1372:∗
1368:Σ
1364:∈
1318:−
1310:∈
1307:ε
1301:⇔
1292:∈
1246:ε
1220:∗
1216:Σ
1212:⊆
1165:−
1161:ε
1142:−
1126:−
1103:−
1063:∗
1059:Σ
1055:∈
1046:Σ
1043:∈
1005:−
989:−
981:∈
975:⇔
964:−
956:∈
947:⇔
941:∈
929:⇔
918:−
901:∈
875:∗
871:Σ
867:∈
830:−
814:−
795:−
756:∗
752:Σ
748:∈
710:∈
700:⇔
688:−
680:∈
652:∗
648:Σ
644:∈
608:∖
584:−
523:∈
514:∣
509:∗
505:Σ
501:∈
481:−
411:∗
407:Σ
403:∈
380:Σ
335:algorithm
257:−
219:∈
210:∣
205:∗
201:Σ
197:∈
177:−
51:−
2902:Category
2742:14126942
2701:14126942
2543:See also
1651:language
1633:alphabet
1236:nullable
2594:1611992
2525:parsing
96:strings
2884:
2740:
2699:
2592:
2413:) = ∅
2387:) ∨ ν(
2363:) ∧ ν(
2339:) ∧ ν(
2246:Here,
1676:, and
1304:
1298:
576:
140:prefix
35:, the
2862:arXiv
2738:S2CID
2720:J ACM
2697:S2CID
2679:J ACM
2619:(PDF)
2590:S2CID
2494:with
2428:if ν(
2409:if ν(
2211:) ∨ (
2178:) ∧ (
1917:*) =
1718:) = {
1418:false
1390:when
71:of a
2882:ISBN
2763:bits
2610:and
2432:) =
2383:= ν(
2359:= ν(
2335:= ν(
2308:= ∅
2305:ν(∅)
2233:= ¬(
2142:∨ ν(
2090:= ∅
2079:= ∅
1886:) ·
1878:) =
1866:and
1847:* \
1843:) =
1808:) ∩
1800:) =
1784:and
1761:) ∪
1753:) =
1737:and
1680:and
1416:and
1388:true
1349:and
1343:tree
2872:doi
2839:doi
2728:doi
2687:doi
2656:doi
2631:doi
2582:doi
2425:= ∅
2418:ν(¬
2396:ν(¬
2279:= ∅
2258:if
2204:= (
2171:= (
2131:= (
2105:= (
2056:= ∅
1925:)*.
1905:of
1835:):
1665:).
1653:of
285:dog
277:cow
269:cat
94:of
73:set
27:In
2904::
2880:.
2870:.
2736:.
2724:11
2722:.
2718:.
2695:.
2683:11
2681:.
2677:.
2625:.
2621:.
2588:.
2576:.
2572:.
2511:.
2461:.
2403:=
2391:)
2376:∨
2372:ν(
2367:)
2352:∧
2348:ν(
2343:)
2330:RS
2328:ν(
2320:=
2317:*)
2313:ν(
2297:=
2290:ν(
2272:ν(
2248:ν(
2240:)
2226:(¬
2218:)
2185:)
2126:RS
2116:*
2102:*)
2040:=
2013:=
1979:=
1971:ua
1909::
1894:),
1876:RS
1870::
1860:RS
1855:),
1839:(¬
1819:"¬
1816:),
1788::
1769:),
1741::
1722:},
1710::
1526::
1077::
770::
666::
624:.
568::
341:.
307:ow
299:at
2890:.
2874::
2864::
2845:.
2841::
2769:.
2767:n
2760:n
2756:A
2744:.
2730::
2703:.
2689::
2662:.
2658::
2637:.
2633::
2627:3
2596:.
2584::
2578:5
2505:R
2500:R
2496:d
2487:R
2483:d
2479:R
2474:R
2470:d
2466:R
2459:R
2456:u
2452:R
2448:u
2434:ε
2430:R
2422:)
2420:R
2411:R
2405:ε
2400:)
2398:R
2389:S
2385:R
2380:)
2378:S
2374:R
2365:S
2361:R
2356:)
2354:S
2350:R
2341:S
2337:R
2332:)
2322:ε
2315:R
2299:ε
2294:)
2292:ε
2284:a
2276:)
2274:a
2264:ε
2260:R
2256:ε
2252:)
2250:R
2238:R
2235:a
2230:)
2228:R
2224:a
2216:S
2213:a
2209:R
2206:a
2201:)
2199:S
2197:∨
2195:R
2193:(
2191:a
2183:S
2180:a
2176:R
2173:a
2168:)
2166:S
2164:∧
2162:R
2160:(
2158:a
2151:S
2148:a
2146:)
2144:R
2140:S
2138:)
2136:R
2133:a
2128:)
2124:(
2122:a
2114:R
2112:)
2110:R
2107:a
2100:R
2098:(
2096:a
2087:∅
2085:a
2075:ε
2072:a
2065:a
2063:≠
2061:b
2052:b
2049:a
2042:ε
2036:a
2033:a
2024:a
2015:R
2009:R
2006:ε
1999:u
1995:a
1990:)
1988:R
1985:u
1983:(
1981:a
1975:R
1973:)
1969:(
1961:R
1959:(
1957:L
1954:u
1950:R
1947:u
1943:u
1939:R
1923:R
1921:(
1919:L
1915:R
1913:(
1911:L
1907:R
1899:R
1897:"
1892:S
1890:(
1888:L
1884:R
1882:(
1880:L
1874:(
1872:L
1868:S
1864:R
1858:"
1853:R
1851:(
1849:L
1845:A
1841:R
1837:L
1833:A
1829:A
1825:R
1821:R
1814:S
1812:(
1810:L
1806:R
1804:(
1802:L
1798:S
1796:∧
1794:R
1792:(
1790:L
1786:S
1782:R
1778:S
1776:∧
1774:R
1772:"
1767:S
1765:(
1763:L
1759:R
1757:(
1755:L
1751:S
1749:∨
1747:R
1745:(
1743:L
1739:S
1735:R
1731:S
1729:∨
1727:R
1725:"
1720:a
1716:a
1714:(
1712:L
1708:a
1704:a
1702:"
1697:L
1690:L
1682:S
1678:R
1674:A
1670:a
1663:R
1661:(
1659:L
1655:R
1647:A
1643:R
1636:A
1608:.
1605:)
1602:S
1597:1
1590:a
1586:(
1583:a
1572:a
1561:)
1558:S
1552:}
1546:{
1543:(
1540:=
1537:S
1501:S
1481:S
1476:1
1469:a
1448:a
1428:a
1404:S
1398:w
1361:w
1326:S
1321:1
1314:w
1295:S
1289:w
1266:S
1209:S
1183:S
1180:=
1173:S
1168:1
1153:)
1150:S
1145:1
1138:u
1134:(
1129:1
1122:a
1118:=
1111:S
1106:1
1099:)
1095:a
1092:u
1089:(
1052:u
1049:,
1040:a
1028:.
1016:)
1013:S
1008:1
1001:u
997:(
992:1
985:v
978:w
972:S
967:1
960:u
953:w
950:v
944:S
938:w
935:v
932:u
926:S
921:1
914:)
910:v
907:u
904:(
898:w
864:w
841:)
838:S
833:1
826:u
822:(
817:1
810:v
806:=
803:S
798:1
791:)
787:v
784:u
781:(
745:v
742:,
739:u
716:.
713:S
707:v
704:u
696:S
691:1
684:u
677:v
641:v
638:,
635:u
612:S
604:}
601:u
598:{
595:=
592:S
587:1
580:u
556:u
529:}
526:S
520:v
517:u
498:v
495:{
492:=
489:S
484:1
477:u
453:u
433:S
400:u
360:S
314:.
311:}
303:,
295:{
292:=
289:}
281:,
273:,
265:{
260:1
253:c
237:.
225:}
222:S
216:v
213:u
194:v
191:{
188:=
185:S
180:1
173:u
149:u
126:S
106:u
82:S
59:S
54:1
47:u
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
