398:"Kleene's theorem". Two other textbooks first prove the expressive equivalence of NFAs and DFAs ("2." and "3.") and then state "Kleene's theorem" as the equivalence between regular expressions and finite automata (the latter said to describe "recognizable languages"). A linguistically oriented text first equates regular grammars ("4." above) with DFAs and NFAs, calls the languages generated by (any of) these "regular", after which it introduces regular expressions which it terms to describe "rational languages", and finally states "Kleene's theorem" as the coincidence of regular and rational languages. Other authors simply
962:
397:
in textbooks. Precisely which one (or which subset) is called such varies between authors. One textbook calls the equivalence of regular expressions and NFAs ("1." and "2." above) "Kleene's theorem". Another textbook calls the equivalence of regular expressions and DFAs ("1." and "3." above)
794:
For a fixed finite alphabet, the theory of the set of all languages â together with strings, membership of a string in a language, and for each character, a function to append the character to a string (and no other operations) â is decidable, and its minimal
2293:. (In fact, Eilenberg defines rational and recognizable subsets of arbitrary monoids; the two notions do not, in general, coincide.) This terminology, while better motivated, never really caught on, and "regular language" is used almost universally.â
2246:
3696:: Representation of events in nerve nets and finite automata. In: Shannon, C.E., McCarthy, J. (eds.) Automata Studies, pp. 3â41. Princeton University Press, Princeton (1956); it is a slightly modified version of his 1951
1686:
229:â„ 0}. Intuitively, it cannot be recognized with a finite automaton, since a finite automaton has finite memory and it cannot remember the exact number of a's. Techniques to prove this fact rigorously are given
2289:'s monograph often use either the term "recognizable language", which refers to the behavior of automata, or "rational language", which refers to important analogies between regular expressions and rational
1840:
791:", still just regular languages can be described, but the universality problem has an exponential space lower bound, and is in fact complete for exponential space with respect to polynomial-time reduction.
1221:
2845:
M. Weyer: Chapter 12 - Decidability of S1S and S2S, p. 219, Theorem 12.26. In: Erich GrÀdel, Wolfgang Thomas, Thomas Wilke (Eds.): Automata, Logics, and
Infinite Games: A Guide to Current Research.
1392:
2693:
916:
2122:
1461:
2977:
3774:
633:
can be obtained by reversing all transitions and interchanging starting and finishing states. This may result in multiple starting states; Δ-transitions can be used to join them.
1305:
1965:
1879:
2285:
over a monoid that is not necessarily free. Howard
Straubing notes in relation to these facts that âThe term "regular language" is a bit unfortunate. Papers influenced by
1906:
1494:
1530:
1077:
559:
1739:
1714:
1340:
2063:
1994:
2141:
2679:
Chapter 1: Regular
Languages, pp. 31â90. Subsection "Decidable Problems Concerning Regular Languages" of section 4.1: Decidable Languages, pp. 152â155.
1766:
2034:
2014:
1926:
1570:
1550:
1256:
1117:
1097:
4094:
297:
3767:
1575:
2654:
845:, since it (trivially) contains the parity problem of determining whether the number of 1 bits in the input is even or odd and this problem is not in
3981:
3760:
3318:
Theoretical computer science: Introduction to
Automata, Computability, Complexity, Algorithmics, Randomization, Communication, and Cryptography
1022:, those that can be described by a regular expression constructed from the empty symbol, letters, concatenation and all Boolean operators (see
379:
Properties 10. and 11. are purely algebraic approaches to define regular languages; a similar set of statements can be formulated for a monoid
3725:
3666:
3375:
3261:
3185:
2941:
2897:
2870:
2821:
2792:
2760:
2582:
3906:
2351:
3996:
2300:
990:
3921:
3136:
1774:
3620:
3590:
3582:
3326:
2846:
2726:
2703:
2664:
2632:
2493:
2395:
249:
4089:
4074:
402:"rational expression" and "regular expressions" as synonymous and do the same with "rational languages" and "regular languages".
3950:
812:
1136:
2391:
2332:
256:
1349:
38:
583:, inverse string homomorphism, and intersection with regular languages. As a consequence they are closed under arbitrary
3967:
3892:
1120:
576:
269:
45:
949:)) equals the class of regular languages. In practice, most nonregular problems are solved by machines taking at least
195:
language {Δ} = Ă* is regular. Other typical examples include the language consisting of all strings over the alphabet {
68:, in the strict sense in theoretical computer science (as opposed to many modern regular expression engines, which are
4064:
1308:
864:
104:
31:
2068:
390:
Some authors use one of the above properties different from "1." as an alternative definition of regular languages.
3960:
3658:
2574:
2485:
2320:
1400:
1008:
Finite languages, those containing only a finite number of words. These are regular languages, as one can create a
293:
2425:
2304:
986:
654:
closure properties, the following problems are also decidable for arbitrarily given deterministic finite automata
4136:
3885:
483:
4141:
4037:
4032:
466:
275:
3701:
2958:
4118:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
1027:
584:
496:
123:
3349:
A finite language shouldn't be confused with a (usually infinite) language generated by a finite automaton.
4048:
3986:
3911:
3526:
3047:(1991). "Constructivity issues in graph algorithms". In Myers, J. Paul Jr.; O'Donnell, Michael J. (eds.).
2684:
977:. The converse is not true: for example, the language consisting of all strings having the same number of
796:
49:
3991:
3939:
3752:
2379:
1261:
998:
974:
450:
2363:
1881:, witnessing the non-regularity of the Dyck language. Care must be taken since some of the eigenvalues
3049:
Constructivity in
Computer Science, Summer Symposium, San Antonio, Texas, USA, June 19-22, Proceedings
1931:
1845:
4084:
4059:
3916:
3877:
2548:
364:
3531:
1967:, but the number of words of even or odd length are of this form; the corresponding eigenvalues are
3693:
1128:
580:
505:
428:
346:
84:
1884:
4069:
4011:
3955:
3234:
1466:
1019:
1013:
1009:
470:
180:
69:
65:
985:'s is context-free but not regular. To prove that a language is not regular, one often uses the
393:
Some of the equivalences above, particularly those among the first four formalisms, are called
3804:
3721:
3662:
3616:
3612:
3586:
3578:
3371:
3332:
3322:
3257:
3181:
2937:
2931:
2914:
2893:
2887:
2866:
2860:
2817:
2788:
2756:
2750:
2722:
2699:
2660:
2628:
2578:
2489:
2308:
1499:
1231:
1046:
970:
950:
800:
538:
88:
3360:
3276:
J. Hartmanis, P. L. Lewis II, and R. E. Stearns. Hierarchies of memory-limited computations.
3165:
2809:
2782:
2251:
The zeta function of a regular language is not in general rational, but that of an arbitrary
4053:
3973:
3819:
3713:
3697:
3672:
3626:
3544:
3536:
3417:
3407:
3218:
3173:
3052:
3044:
2992:
2670:
2638:
2608:
2600:
2588:
2499:
2474:
2367:
2312:
2286:
2282:
2241:{\displaystyle \zeta _{L}(z)=\exp \left({\sum _{n\geq 0}s_{L}(n){\frac {z^{n}}{n}}}\right).}
832:
816:
368:
308:
304:
76:
3230:
1318:
4016:
3931:
3898:
3814:
3787:
3783:
3676:
3630:
3548:
3421:
3226:
3040:
2674:
2642:
2612:
2592:
2503:
2296:
2281:. Likewise, the notion of a recognizable language (by a finite automaton) has namesake as
2277:
generalizes the notion (of regular/rational language) to monoids that are not necessarily
2252:
2039:
1970:
1023:
776:
263:
92:
61:
3278:
Proceedings of the 6th Annual IEEE Symposium on
Switching Circuit Theory and Logic Design
2715:
3118:
The
Equivalence Problem for Regular Expressions with Squaring Requires Exponential Space
1748:
1719:
1694:
835:
that can be solved in constant space (the space used is independent of the input size).
4027:
3809:
3791:
3742:
3605:
3206:
2650:
2268:
2264:
2019:
1999:
1911:
1769:
1555:
1535:
1343:
1241:
1102:
1082:
942:
930:
588:
287:
281:
3540:
3396:"A necessary condition for the rationality of the zeta function of a regular language"
2997:
799:
consists precisely of regular languages. For a binary alphabet, the theory is called
598:
with a regular language. Even more, regular languages are closed under quotients with
4130:
4112:
3412:
3395:
3202:
1742:
650:, it is decidable whether they accept the same language. As a consequence, using the
531:
3517:
Berstel, Jean; Reutenauer, Christophe (1990). "Zeta functions of formal languages".
3238:
145:) is a regular language. Due to this, the empty string language {Δ} is also regular.
2620:
2566:
2290:
2274:
418:
192:
3135:
L. J. Stockmeyer; A. R. Meyer (1973). "Word
Problems Requiring Exponential Time".
1681:{\displaystyle s_{L}(n)=p_{1}(n)\lambda _{1}^{n}+\dotsb +p_{k}(n)\lambda _{k}^{n}}
3747:
3172:. Lecture Notes in Computer Science. Vol. 2500. Springer. pp. 207â230.
37:"Kleene's theorem" redirects here. For his theorems for recursive functions, see
4079:
4001:
3926:
3051:. Lecture Notes in Computer Science. Vol. 613. Springer. pp. 150â158.
2278:
1031:
961:
772:
564:
357:
142:
75:
Alternatively, a regular language can be defined as a language recognised by a
17:
2573:. Encyclopedia of Mathematics and Its Applications. Vol. 137. Cambridge:
1395:
858:
3256:(1. publ. ed.). Ithaca, NY: Association for Symbolic Logic. p. 75.
3177:
3116:
2263:
The notion of a regular language has been generalized to infinite words (see
3336:
3124:. 13th Annual IEEE Symp. on Switching and Automata Theory. pp. 125â129.
2319:. Also in this context, Kleene's theorem finds a generalization called the
3717:
1908:
could have the same magnitude. For example, the number of words of length
218:
A simple example of a language that is not regular is the set of strings {
3316:
315:
79:. The equivalence of regular expressions and finite automata is known as
2607:. Pure and Applied Mathematics. Vol. 58. New York: Academic Press.
775:
already for a singleton alphabet. For larger alphabets, that problem is
3611:. Progress in Theoretical Computer Science. Basel: BirkhÀuser. p.
3469:
3222:
3078:
Hopcroft, Ullman (1979), Theorem 3.8, p.64; see also
Theorem 3.10, p.67
3056:
2544:
1312:
3483:
3444:
3290:
2836:
Eilenberg (1974), p. 16 (Example II, 2.8) and p. 25 (Example II, 5.2).
3712:. Lecture Notes in Computer Science. Vol. 1987. pp. 39â50.
2933:
Syntactic and
Structural Pattern Recognition: Theory and Applications
2311:. In this algebraic context, the regular languages (corresponding to
828:
339:
245:
it is the language of a regular expression (by the above definition)
207:'s, or the language consisting of all strings of the form: several
4042:
1745:
of strings of balanced parentheses. The number of words of length
241:
A regular language satisfies the following equivalent properties:
2713:
Alfred V. Aho and John E. Hopcroft and Jeffrey D. Ullman (1974).
1996:. In general, for every regular language there exists a constant
3710:
Trends, Techniques, and Problems in Theoretical Computer Science
1835:{\displaystyle C_{n}\sim {\frac {4^{n}}{n^{3/2}{\sqrt {\pi }}}}}
409:
originates from a 1951 technical report where Kleene introduced
27:
Formal language that can be expressed using a regular expression
3756:
3209:(1984). "Parity, circuits, and the polynomial-time hierarchy".
2814:
Handbook of Formal Languages: Volume 1. Word, Language, Grammar
840:
425:
in a different meaning at first (referring to what is called
4111:
Each category of languages, except those marked by a , is a
1928:
in the language of all even binary words is not of the form
2695:
Introduction to Automata Theory, Languages, and Computation
461:
are regular, so is the result of the following operations:
367:
is finite. (This number equals the number of states of the
3657:. Translated from the French by Reuben Thomas. Cambridge:
2959:
Representation of Events in Nerve Nets and Finite Automata
2889:
Automatic Sequences: Theory, Applications, Generalizations
2484:. Cambridge Studies in Advanced Mathematics. Vol. 1.
3484:"Number of words of a given length in a regular language"
2964:(Research Memorandum). U.S. Air Force / RAND Corporation.
2299:
is another generalization, this time in the context of a
1716:
can be proved by counting the words of a given length in
625:. Given a nondeterministic finite automaton to recognize
3069:
Hopcroft, Ullman (1979), Chapter 3, Exercise 3.4g, p. 72
1216:{\displaystyle S_{L}(z)=\sum _{n\geq 0}s_{L}(n)z^{n}\ .}
3434:
Flajolet & Sedgweick, section V.3.1, equation (13).
2415:
4. â 2. see Hopcroft, Ullman (1979), Theorem 9.1, p.218
2406:
2. â 4. see Hopcroft, Ullman (1979), Theorem 9.2, p.219
779:. If regular expressions are extended to allow also a
230:
72:
that allow the recognition of non-regular languages).
3708:
Sakarovitch, J (1987). "Kleene's theorem revisited".
3607:
Finite automata, formal logic, and circuit complexity
2916:
Discrete Mathematics and Its Applications 7th edition
2144:
2071:
2042:
2022:
2002:
1973:
1934:
1914:
1887:
1848:
1777:
1751:
1722:
1697:
1578:
1558:
1538:
1502:
1469:
1403:
1387:{\displaystyle \lambda _{1},\,\ldots ,\,\lambda _{k}}
1352:
1321:
1264:
1244:
1139:
1105:
1085:
1049:
867:
819:
of all regular languages is sometimes referred to as
771:
For regular expressions, the universality problem is
541:
3445:"Number of words in the regular language $ (00)^*$ "
453:
under various operations, that is, if the languages
191:
All finite languages are regular; in particular the
3366:. In Jörg Flum; Erich GrÀdel; Thomas Wilke (eds.).
3087:
Aho, Hopcroft, Ullman (1974), Exercise 10.14, p.401
2315:-weighted rational expressions) are usually called
91:, regular languages are the languages generated by
3604:
3138:Proc. 5th ann. symp. on Theory of computing (STOC)
2714:
2240:
2116:
2057:
2028:
2008:
1988:
1959:
1920:
1900:
1873:
1834:
1760:
1733:
1708:
1680:
1564:
1544:
1524:
1488:
1455:
1386:
1334:
1299:
1250:
1215:
1111:
1091:
1071:
1004:Important subclasses of regular languages include
910:
553:
3096:Aho, Hopcroft, Ullman (1974), Theorem 10.14, p399
387:leads to the concept of a recognizable language.
183:for syntax and semantics of regular expressions.
2752:The Oxford Handbook of Computational Linguistics
2571:Noncommutative rational series with applications
965:Regular language in classes of Chomsky hierarchy
911:{\displaystyle \{0^{n}1^{n}:n\in \mathbb {N} \}}
3593:), the latter with two chapters by Bret Tilson.
415:"any suggestions as to a more descriptive term"
3291:"How to prove that a language is not regular?"
2930:Horst Bunke; Alberto Sanfeliu (January 1990).
2812:. In Grzegorz Rozenberg; Arto Salomaa (eds.).
2717:The Design and Analysis of Computer Algorithms
2117:{\displaystyle C_{a}m^{p_{a}}\lambda _{a}^{m}}
1238:is regular. Hence for every regular language
3768:
3115:A.R. Meyer & L.J. Stockmeyer (Oct 1972).
3105:Hopcroft, Ullman (1979), Theorem 13.15, p.351
2859:Robert Sedgewick; Kevin Daniel Wayne (2011).
2688:: Symbolic Combinatorics. Online book, 2002.
1456:{\displaystyle p_{1}(x),\,\ldots ,\,p_{k}(x)}
973:, one notices that every regular language is
929:regular, it requires a machine with at least
421:, in his 1959 seminal article, used the term
8:
3368:Logic and automata: history and perspectives
2886:Jean-Paul Allouche; Jeffrey Shallit (2003).
2865:. Addison-Wesley Professional. p. 794.
2776:
2774:
2772:
2744:
2742:
2692:John E. Hopcroft; Jeffrey D. Ullman (1979).
905:
868:
103:The collection of regular languages over an
30:For natural language that is regulated, see
4090:Counter-free (with aperiodic finite monoid)
3507:Flajolet & Sedgewick (2002) Theorem V.3
2892:. Cambridge University Press. p. 129.
2605:Automata, Languages, and Machines. Volume A
1034:: this class includes all finite languages.
941:is the input size). In other words, DSPACE(
111:The empty language Ă is a regular language.
3800:
3775:
3761:
3753:
3389:
3387:
2978:"On Certain Formal Properties of Grammars"
1691:Thus, non-regularity of certain languages
3530:
3411:
2996:
2656:Introduction to the Theory of Computation
2219:
2213:
2198:
2182:
2177:
2149:
2143:
2108:
2103:
2091:
2086:
2076:
2070:
2041:
2021:
2001:
1972:
1951:
1933:
1913:
1892:
1886:
1865:
1847:
1822:
1812:
1808:
1797:
1791:
1782:
1776:
1750:
1721:
1696:
1672:
1667:
1648:
1629:
1624:
1605:
1583:
1577:
1557:
1537:
1507:
1501:
1480:
1468:
1438:
1433:
1426:
1408:
1402:
1378:
1373:
1366:
1357:
1351:
1326:
1320:
1285:
1269:
1263:
1243:
1201:
1182:
1166:
1144:
1138:
1104:
1084:
1054:
1048:
1039:The number of words in a regular language
901:
900:
885:
875:
866:
540:
363:the number of equivalence classes of its
3154:Hopcroft, Ullman (1979), Corollary p.353
2919:. McGraw-Hill Science. pp. 873â880.
2755:. Oxford University Press. p. 754.
2682:Philippe Flajolet and Robert Sedgewick,
960:
642:Given two deterministic finite automata
3254:Logical foundations of proof complexity
2738:
2343:
994:
969:To locate the regular languages in the
651:
3982:Linear context-free rewriting language
3252:Cook, Stephen; Nguyen, Phuong (2010).
2551:for an illustration of the proof idea.
1226:The generating function of a language
369:minimal deterministic finite automaton
175:No other languages over ÎŁ are regular.
172:(concatenation) are regular languages.
3907:Linear context-free rewriting systems
3561:Berstel & Reutenauer (2011) p.222
3470:"Proof of theorem for arbitrary DFAs"
1768:in the Dyck language is equal to the
1079:denote the number of words of length
993:. Other approaches include using the
857:, because the nonregular language of
107:ÎŁ is defined recursively as follows:
7:
3643:Berstel & Reutenauer (2011) p.47
3359:Volker Diekert; Paul Gastin (2008).
3170:Automata, Logics, and Infinite Games
997:of regular languages or quantifying
383:â ÎŁ. In this case, equivalence over
2301:formal power series over a semiring
4115:of the category directly above it.
1300:{\displaystyle s_{L}(n)_{n\geq 0}}
286:it can be accepted by a read-only
268:it is the language accepted by an
203:} which contain an even number of
25:
3573:Automata, languages, and machines
3541:10.1090/s0002-9947-1990-0998123-x
3361:"First-order definable languages"
2936:. World Scientific. p. 248.
2847:Lecture Notes in Computer Science
2569:; Reutenauer, Christophe (2011).
2352:Thompson's construction algorithm
957:Location in the Chomsky hierarchy
274:it is the language accepted by a
255:it is the language accepted by a
250:nondeterministic finite automaton
248:it is the language accepted by a
3012:Chomsky 1959, Footnote 10, p.150
2957:Stephen Cole Kleene (Dec 1951).
2625:Jewels of Formal Language Theory
2036:, the number of words of length
1960:{\displaystyle p(n)\lambda ^{n}}
1874:{\displaystyle p(n)\lambda ^{n}}
467:set-theoretic Boolean operations
298:BĂŒchiâElgotâTrakhtenbrot theorem
813:computational complexity theory
130: } is a regular language.
3370:. Amsterdam University Press.
2787:. CRC Press. pp. 98â103.
2472:3. â 11. see the proof in the
2333:Induction of regular languages
2303:. This approach gives rise to
2210:
2204:
2161:
2155:
1944:
1938:
1858:
1852:
1660:
1654:
1617:
1611:
1595:
1589:
1519:
1513:
1450:
1444:
1420:
1414:
1282:
1275:
1194:
1188:
1156:
1150:
1066:
1060:
1016:of every word in the language.
621:the reverse (or mirror image)
257:deterministic finite automaton
83:(after American mathematician
1:
3653:Sakarovitch, Jacques (2009).
3166:"Decidability of S1S and S2S"
2998:10.1016/S0019-9958(59)90362-6
2321:Kleene-SchĂŒtzenberger theorem
2305:weighted rational expressions
1741:. Consider, for example, the
861:, or the nonregular language
433:today), but noticed that his
3413:10.1016/0304-3975(89)90159-x
3321:. Springer. pp. 76â77.
2543:. Deciding this property is
1901:{\displaystyle \lambda _{i}}
1121:ordinary generating function
937:) space to recognize (where
437:were equivalent to Kleene's
270:alternating finite automaton
156:are regular languages, then
46:theoretical computer science
3655:Elements of automata theory
3211:Mathematical Systems Theory
1842:, which is not of the form
1489:{\displaystyle n\geq n_{0}}
32:List of language regulators
4158:
3997:Deterministic context-free
3922:Deterministic context-free
3700:report of the same title,
3659:Cambridge University Press
3603:Straubing, Howard (1994).
3577:in two volumes "A" (1974,
2575:Cambridge University Press
2486:Cambridge University Press
2478:article, and see p.160 in
2330:
1311:; that is, there exist an
918:can both be recognized in
662:, with accepted languages
585:finite state transductions
449:The regular languages are
294:monadic second-order logic
39:Kleene's recursion theorem
36:
29:
4108:
4070:Nondeterministic pushdown
3798:
3315:HromkoviÄ, Juraj (2004).
3003:Here: Definition 8, p.149
2482:Algebraic automata theory
2480:Holcombe, W.M.L. (1982).
280:it can be generated by a
262:it can be generated by a
64:that can be defined by a
3178:10.1007/3-540-36387-4_12
2816:. Springer. p. 41.
1525:{\displaystyle s_{L}(n)}
1072:{\displaystyle s_{L}(n)}
787:" denoting the same as "
554:{\displaystyle K\circ L}
520:the regular operations:
435:"finite state languages"
413:and explicitly welcomed
276:two-way finite automaton
2985:Information and Control
2781:Mark V. Lawson (2003).
797:elementary substructure
638:Decidability properties
211:'s followed by several
137:is a regular language,
70:augmented with features
4075:Deterministic pushdown
3951:Recursively enumerable
3394:Honkala, Juha (1989).
2913:Kenneth Rosen (2011).
2749:Ruslan Mitkov (2003).
2685:Analytic Combinatorics
2327:Learning from examples
2242:
2118:
2059:
2030:
2010:
1990:
1961:
1922:
1902:
1875:
1836:
1762:
1735:
1710:
1682:
1566:
1546:
1526:
1490:
1457:
1388:
1336:
1301:
1252:
1217:
1113:
1093:
1073:
966:
912:
555:
50:formal language theory
3718:10.1007/3540185356_29
2976:Noam Chomsky (1959).
2627:. Pitman Publishing.
2426:MyhillâNerode theorem
2394:is stronger than the
2380:powerset construction
2243:
2119:
2060:
2031:
2011:
1991:
1962:
1923:
1903:
1876:
1837:
1763:
1736:
1711:
1683:
1567:
1547:
1527:
1491:
1458:
1389:
1337:
1335:{\displaystyle n_{0}}
1302:
1253:
1218:
1114:
1094:
1074:
999:Kolmogorov complexity
987:MyhillâNerode theorem
964:
945:(log log
933:(log log
913:
849:. On the other hand,
556:
405:Apparently, the term
292:it can be defined in
237:Equivalent formalisms
4060:Tree stack automaton
3519:Trans. Am. Math. Soc
3488:cs.stackexchange.com
3449:cs.stackexchange.com
3295:cs.stackexchange.com
3280:, pp. 179â190. 1965.
3164:Weyer, Mark (2002).
3144:. ACM. pp. 1â9.
3045:Langston, Michael A.
2849:2500, Springer 2002.
2549:File:RegSubsetNP.pdf
2267:) and to trees (see
2142:
2069:
2058:{\displaystyle dm+a}
2040:
2020:
2000:
1989:{\displaystyle 2,-2}
1971:
1932:
1912:
1885:
1846:
1775:
1749:
1720:
1695:
1576:
1556:
1536:
1500:
1467:
1463:such that for every
1401:
1350:
1319:
1262:
1242:
1137:
1103:
1083:
1047:
865:
539:
365:syntactic congruence
314:, meaning it is the
3968:range concatenation
3893:range concatenation
3041:Fellows, Michael R.
3030:Salomaa (1981) p.27
3021:Salomaa (1981) p.28
2810:"Regular languages"
2113:
1677:
1634:
1532:of words of length
1129:formal power series
1020:Star-free languages
629:, an automaton for
614:is regular for any
581:string homomorphism
506:relative complement
429:Chomsky normal form
347:monoid homomorphism
122:belongs to ÎŁ), the
85:Stephen Cole Kleene
3571:Samuel Eilenberg.
3400:Theor. Comput. Sci
3223:10.1007/BF01744431
3057:10.1007/BFB0021088
2721:. Addison-Wesley.
2698:. Addison-Wesley.
2659:. PWS Publishing.
2390:3. â 2. since the
2364:Kleene's algorithm
2317:rational languages
2238:
2193:
2114:
2099:
2065:is asymptotically
2055:
2026:
2016:such that for all
2006:
1986:
1957:
1918:
1898:
1871:
1832:
1761:{\displaystyle 2n}
1758:
1734:{\displaystyle L'}
1731:
1709:{\displaystyle L'}
1706:
1678:
1663:
1620:
1562:
1542:
1522:
1486:
1453:
1384:
1332:
1309:constant-recursive
1297:
1248:
1213:
1177:
1109:
1089:
1069:
1010:regular expression
995:closure properties
967:
908:
807:Complexity results
750:Membership: given
551:
445:Closure properties
181:regular expression
66:regular expression
4124:
4123:
4103:
4102:
4065:Embedded pushdown
3961:Context-sensitive
3886:Context-sensitive
3820:Abstract machines
3805:Chomsky hierarchy
3727:978-3-540-18535-2
3668:978-0-521-84425-3
3585:) and "B" (1976,
3575:. Academic Press.
3377:978-90-5356-576-6
3263:978-0-521-51729-4
3187:978-3-540-00388-5
2943:978-9971-5-0566-0
2899:978-0-521-82332-6
2872:978-0-321-57351-3
2823:978-3-540-60420-4
2808:Sheng Yu (1997).
2794:978-1-58488-255-8
2762:978-0-19-927634-9
2601:Eilenberg, Samuel
2584:978-0-521-19022-0
2392:former definition
2309:weighted automata
2228:
2178:
2029:{\displaystyle a}
2009:{\displaystyle d}
1921:{\displaystyle n}
1830:
1827:
1565:{\displaystyle L}
1545:{\displaystyle n}
1251:{\displaystyle L}
1232:rational function
1209:
1162:
1112:{\displaystyle L}
1092:{\displaystyle n}
971:Chomsky hierarchy
951:logarithmic space
925:If a language is
853:does not contain
833:decision problems
781:squaring operator
738:Universality: is
705:Disjointness: is
99:Formal definition
89:Chomsky hierarchy
58:rational language
16:(Redirected from
4149:
4137:Formal languages
4119:
4116:
4080:Visibly pushdown
4054:Thread automaton
4002:Visibly pushdown
3970:
3927:Visibly pushdown
3895:
3882:(no common name)
3801:
3788:formal languages
3777:
3770:
3763:
3754:
3731:
3698:RAND Corporation
3681:
3680:
3650:
3644:
3641:
3635:
3634:
3610:
3600:
3594:
3576:
3568:
3562:
3559:
3553:
3552:
3534:
3514:
3508:
3505:
3499:
3498:
3496:
3494:
3480:
3474:
3473:
3466:
3460:
3459:
3457:
3455:
3441:
3435:
3432:
3426:
3425:
3415:
3391:
3382:
3381:
3365:
3356:
3350:
3347:
3341:
3340:
3312:
3306:
3305:
3303:
3301:
3287:
3281:
3274:
3268:
3267:
3249:
3243:
3242:
3201:Furst, Merrick;
3198:
3192:
3191:
3161:
3155:
3152:
3146:
3145:
3143:
3132:
3126:
3125:
3123:
3112:
3106:
3103:
3097:
3094:
3088:
3085:
3079:
3076:
3070:
3067:
3061:
3060:
3037:
3031:
3028:
3022:
3019:
3013:
3010:
3004:
3002:
3000:
2982:
2973:
2967:
2965:
2963:
2954:
2948:
2947:
2927:
2921:
2920:
2910:
2904:
2903:
2883:
2877:
2876:
2856:
2850:
2843:
2837:
2834:
2828:
2827:
2805:
2799:
2798:
2778:
2767:
2766:
2746:
2732:
2720:
2709:
2678:
2646:
2616:
2596:
2552:
2547:in general; see
2514:
2508:
2507:
2475:Syntactic monoid
2470:
2464:
2434:
2428:
2424:3. â 10. by the
2422:
2416:
2413:
2407:
2404:
2398:
2388:
2382:
2376:
2370:
2360:
2354:
2348:
2283:recognizable set
2247:
2245:
2244:
2239:
2234:
2230:
2229:
2224:
2223:
2214:
2203:
2202:
2192:
2154:
2153:
2123:
2121:
2120:
2115:
2112:
2107:
2098:
2097:
2096:
2095:
2081:
2080:
2064:
2062:
2061:
2056:
2035:
2033:
2032:
2027:
2015:
2013:
2012:
2007:
1995:
1993:
1992:
1987:
1966:
1964:
1963:
1958:
1956:
1955:
1927:
1925:
1924:
1919:
1907:
1905:
1904:
1899:
1897:
1896:
1880:
1878:
1877:
1872:
1870:
1869:
1841:
1839:
1838:
1833:
1831:
1829:
1828:
1823:
1821:
1820:
1816:
1802:
1801:
1792:
1787:
1786:
1767:
1765:
1764:
1759:
1740:
1738:
1737:
1732:
1730:
1715:
1713:
1712:
1707:
1705:
1687:
1685:
1684:
1679:
1676:
1671:
1653:
1652:
1633:
1628:
1610:
1609:
1588:
1587:
1571:
1569:
1568:
1563:
1551:
1549:
1548:
1543:
1531:
1529:
1528:
1523:
1512:
1511:
1495:
1493:
1492:
1487:
1485:
1484:
1462:
1460:
1459:
1454:
1443:
1442:
1413:
1412:
1393:
1391:
1390:
1385:
1383:
1382:
1362:
1361:
1341:
1339:
1338:
1333:
1331:
1330:
1306:
1304:
1303:
1298:
1296:
1295:
1274:
1273:
1257:
1255:
1254:
1249:
1222:
1220:
1219:
1214:
1207:
1206:
1205:
1187:
1186:
1176:
1149:
1148:
1118:
1116:
1115:
1110:
1098:
1096:
1095:
1090:
1078:
1076:
1075:
1070:
1059:
1058:
917:
915:
914:
909:
904:
890:
889:
880:
879:
817:complexity class
684:Containment: is
680:, respectively:
606:is regular then
571:
562:
560:
558:
557:
552:
529:
516:
503:
494:
481:
439:"regular events"
411:"regular events"
395:Kleene's theorem
309:syntactic monoid
81:Kleene's theorem
77:finite automaton
54:regular language
21:
4157:
4156:
4152:
4151:
4150:
4148:
4147:
4146:
4142:Finite automata
4127:
4126:
4125:
4120:
4117:
4110:
4104:
4099:
4021:
3965:
3944:
3890:
3871:
3794:
3792:formal grammars
3784:Automata theory
3781:
3738:
3728:
3707:
3690:
3688:Further reading
3685:
3684:
3669:
3652:
3651:
3647:
3642:
3638:
3623:
3602:
3601:
3597:
3570:
3569:
3565:
3560:
3556:
3532:10.1.1.309.3005
3516:
3515:
3511:
3506:
3502:
3492:
3490:
3482:
3481:
3477:
3468:
3467:
3463:
3453:
3451:
3443:
3442:
3438:
3433:
3429:
3393:
3392:
3385:
3378:
3363:
3358:
3357:
3353:
3348:
3344:
3329:
3314:
3313:
3309:
3299:
3297:
3289:
3288:
3284:
3275:
3271:
3264:
3251:
3250:
3246:
3207:Sipser, Michael
3200:
3199:
3195:
3188:
3163:
3162:
3158:
3153:
3149:
3141:
3134:
3133:
3129:
3121:
3114:
3113:
3109:
3104:
3100:
3095:
3091:
3086:
3082:
3077:
3073:
3068:
3064:
3039:
3038:
3034:
3029:
3025:
3020:
3016:
3011:
3007:
2980:
2975:
2974:
2970:
2961:
2956:
2955:
2951:
2944:
2929:
2928:
2924:
2912:
2911:
2907:
2900:
2885:
2884:
2880:
2873:
2858:
2857:
2853:
2844:
2840:
2835:
2831:
2824:
2807:
2806:
2802:
2795:
2784:Finite Automata
2780:
2779:
2770:
2763:
2748:
2747:
2740:
2735:
2729:
2712:
2706:
2691:
2667:
2651:Sipser, Michael
2649:
2635:
2619:
2599:
2585:
2565:
2561:
2556:
2555:
2542:
2533:
2524:
2515:
2511:
2496:
2479:
2471:
2467:
2451:if and only if
2443:is defined as:
2435:
2431:
2423:
2419:
2414:
2410:
2405:
2401:
2389:
2385:
2378:2. â 3. by the
2377:
2373:
2361:
2357:
2349:
2345:
2340:
2335:
2329:
2297:Rational series
2261:
2259:Generalizations
2253:cyclic language
2215:
2194:
2173:
2145:
2140:
2139:
2087:
2082:
2072:
2067:
2066:
2038:
2037:
2018:
2017:
1998:
1997:
1969:
1968:
1947:
1930:
1929:
1910:
1909:
1888:
1883:
1882:
1861:
1844:
1843:
1804:
1803:
1793:
1778:
1773:
1772:
1747:
1746:
1723:
1718:
1717:
1698:
1693:
1692:
1644:
1601:
1579:
1574:
1573:
1554:
1553:
1534:
1533:
1503:
1498:
1497:
1476:
1465:
1464:
1434:
1404:
1399:
1398:
1374:
1353:
1348:
1347:
1322:
1317:
1316:
1281:
1265:
1260:
1259:
1240:
1239:
1197:
1178:
1140:
1135:
1134:
1101:
1100:
1081:
1080:
1050:
1045:
1044:
1041:
1028:complementation
1024:algebra of sets
959:
881:
871:
863:
862:
809:
777:PSPACE-complete
766:
746:
734:
722:
713:
701:
692:
679:
670:
640:
567:
537:
536:
534:
521:
508:
499:
486:
473:
447:
360:on its alphabet
307:by some finite
264:regular grammar
239:
189:
101:
93:Type-3 grammars
62:formal language
56:(also called a
42:
35:
28:
23:
22:
18:Finite language
15:
12:
11:
5:
4155:
4153:
4145:
4144:
4139:
4129:
4128:
4122:
4121:
4109:
4106:
4105:
4101:
4100:
4098:
4097:
4095:Acyclic finite
4092:
4087:
4082:
4077:
4072:
4067:
4062:
4056:
4051:
4046:
4045:Turing Machine
4040:
4038:Linear-bounded
4035:
4030:
4028:Turing machine
4024:
4022:
4020:
4019:
4014:
4009:
4004:
3999:
3994:
3989:
3987:Tree-adjoining
3984:
3979:
3976:
3971:
3963:
3958:
3953:
3947:
3945:
3943:
3942:
3937:
3934:
3929:
3924:
3919:
3914:
3912:Tree-adjoining
3909:
3904:
3901:
3896:
3888:
3883:
3880:
3874:
3872:
3870:
3869:
3866:
3863:
3860:
3857:
3854:
3851:
3848:
3845:
3842:
3839:
3836:
3833:
3830:
3826:
3823:
3822:
3817:
3812:
3807:
3799:
3796:
3795:
3782:
3780:
3779:
3772:
3765:
3757:
3751:
3750:
3743:Complexity Zoo
3737:
3736:External links
3734:
3733:
3732:
3726:
3705:
3689:
3686:
3683:
3682:
3667:
3661:. p. 86.
3645:
3636:
3621:
3595:
3563:
3554:
3525:(2): 533â546.
3509:
3500:
3475:
3461:
3436:
3427:
3406:(3): 341â347.
3383:
3376:
3351:
3342:
3327:
3307:
3282:
3269:
3262:
3244:
3203:Saxe, James B.
3193:
3186:
3156:
3147:
3127:
3107:
3098:
3089:
3080:
3071:
3062:
3032:
3023:
3014:
3005:
2991:(2): 137â167.
2968:
2949:
2942:
2922:
2905:
2898:
2878:
2871:
2851:
2838:
2829:
2822:
2800:
2793:
2768:
2761:
2737:
2736:
2734:
2733:
2727:
2710:
2704:
2689:
2680:
2665:
2647:
2633:
2617:
2597:
2583:
2562:
2560:
2557:
2554:
2553:
2538:
2529:
2520:
2509:
2494:
2465:
2429:
2417:
2408:
2399:
2383:
2371:
2355:
2342:
2341:
2339:
2336:
2331:Main article:
2328:
2325:
2269:tree automaton
2260:
2257:
2249:
2248:
2237:
2233:
2227:
2222:
2218:
2212:
2209:
2206:
2201:
2197:
2191:
2188:
2185:
2181:
2176:
2172:
2169:
2166:
2163:
2160:
2157:
2152:
2148:
2131:of a language
2111:
2106:
2102:
2094:
2090:
2085:
2079:
2075:
2054:
2051:
2048:
2045:
2025:
2005:
1985:
1982:
1979:
1976:
1954:
1950:
1946:
1943:
1940:
1937:
1917:
1895:
1891:
1868:
1864:
1860:
1857:
1854:
1851:
1826:
1819:
1815:
1811:
1807:
1800:
1796:
1790:
1785:
1781:
1770:Catalan number
1757:
1754:
1729:
1726:
1704:
1701:
1675:
1670:
1666:
1662:
1659:
1656:
1651:
1647:
1643:
1640:
1637:
1632:
1627:
1623:
1619:
1616:
1613:
1608:
1604:
1600:
1597:
1594:
1591:
1586:
1582:
1561:
1541:
1521:
1518:
1515:
1510:
1506:
1483:
1479:
1475:
1472:
1452:
1449:
1446:
1441:
1437:
1432:
1429:
1425:
1422:
1419:
1416:
1411:
1407:
1381:
1377:
1372:
1369:
1365:
1360:
1356:
1329:
1325:
1294:
1291:
1288:
1284:
1280:
1277:
1272:
1268:
1247:
1224:
1223:
1212:
1204:
1200:
1196:
1193:
1190:
1185:
1181:
1175:
1172:
1169:
1165:
1161:
1158:
1155:
1152:
1147:
1143:
1108:
1088:
1068:
1065:
1062:
1057:
1053:
1040:
1037:
1036:
1035:
1017:
958:
955:
907:
903:
899:
896:
893:
888:
884:
878:
874:
870:
808:
805:
769:
768:
762:
748:
742:
736:
730:
726:Emptiness: is
724:
718:
709:
703:
697:
688:
675:
666:
639:
636:
635:
634:
619:
602:languages: If
573:
550:
547:
544:
518:
446:
443:
377:
376:
361:
334:} of a subset
301:
290:
288:Turing machine
284:
282:prefix grammar
278:
272:
266:
260:
253:
246:
238:
235:
188:
185:
177:
176:
173:
146:
131:
112:
100:
97:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
4154:
4143:
4140:
4138:
4135:
4134:
4132:
4114:
4113:proper subset
4107:
4096:
4093:
4091:
4088:
4086:
4083:
4081:
4078:
4076:
4073:
4071:
4068:
4066:
4063:
4061:
4057:
4055:
4052:
4050:
4047:
4044:
4041:
4039:
4036:
4034:
4031:
4029:
4026:
4025:
4023:
4018:
4015:
4013:
4010:
4008:
4005:
4003:
4000:
3998:
3995:
3993:
3990:
3988:
3985:
3983:
3980:
3977:
3975:
3972:
3969:
3964:
3962:
3959:
3957:
3954:
3952:
3949:
3948:
3946:
3941:
3940:Non-recursive
3938:
3935:
3933:
3930:
3928:
3925:
3923:
3920:
3918:
3915:
3913:
3910:
3908:
3905:
3902:
3900:
3897:
3894:
3889:
3887:
3884:
3881:
3879:
3876:
3875:
3873:
3867:
3864:
3861:
3858:
3855:
3852:
3849:
3846:
3843:
3840:
3837:
3834:
3831:
3828:
3827:
3825:
3824:
3821:
3818:
3816:
3813:
3811:
3808:
3806:
3803:
3802:
3797:
3793:
3789:
3785:
3778:
3773:
3771:
3766:
3764:
3759:
3758:
3755:
3749:
3745:
3744:
3740:
3739:
3735:
3729:
3723:
3719:
3715:
3711:
3706:
3703:
3699:
3695:
3692:
3691:
3687:
3678:
3674:
3670:
3664:
3660:
3656:
3649:
3646:
3640:
3637:
3632:
3628:
3624:
3622:3-7643-3719-2
3618:
3614:
3609:
3608:
3599:
3596:
3592:
3591:9780080873756
3588:
3584:
3583:9780080873749
3580:
3574:
3567:
3564:
3558:
3555:
3550:
3546:
3542:
3538:
3533:
3528:
3524:
3520:
3513:
3510:
3504:
3501:
3489:
3485:
3479:
3476:
3471:
3465:
3462:
3450:
3446:
3440:
3437:
3431:
3428:
3423:
3419:
3414:
3409:
3405:
3401:
3397:
3390:
3388:
3384:
3379:
3373:
3369:
3362:
3355:
3352:
3346:
3343:
3338:
3334:
3330:
3328:3-540-14015-8
3324:
3320:
3319:
3311:
3308:
3296:
3292:
3286:
3283:
3279:
3273:
3270:
3265:
3259:
3255:
3248:
3245:
3240:
3236:
3232:
3228:
3224:
3220:
3216:
3212:
3208:
3204:
3197:
3194:
3189:
3183:
3179:
3175:
3171:
3167:
3160:
3157:
3151:
3148:
3140:
3139:
3131:
3128:
3120:
3119:
3111:
3108:
3102:
3099:
3093:
3090:
3084:
3081:
3075:
3072:
3066:
3063:
3058:
3054:
3050:
3046:
3042:
3036:
3033:
3027:
3024:
3018:
3015:
3009:
3006:
2999:
2994:
2990:
2986:
2979:
2972:
2969:
2960:
2953:
2950:
2945:
2939:
2935:
2934:
2926:
2923:
2918:
2917:
2909:
2906:
2901:
2895:
2891:
2890:
2882:
2879:
2874:
2868:
2864:
2863:
2855:
2852:
2848:
2842:
2839:
2833:
2830:
2825:
2819:
2815:
2811:
2804:
2801:
2796:
2790:
2786:
2785:
2777:
2775:
2773:
2769:
2764:
2758:
2754:
2753:
2745:
2743:
2739:
2730:
2728:9780201000290
2724:
2719:
2718:
2711:
2707:
2705:0-201-02988-X
2701:
2697:
2696:
2690:
2687:
2686:
2681:
2676:
2672:
2668:
2666:0-534-94728-X
2662:
2658:
2657:
2652:
2648:
2644:
2640:
2636:
2634:0-273-08522-0
2630:
2626:
2622:
2621:Salomaa, Arto
2618:
2614:
2610:
2606:
2602:
2598:
2594:
2590:
2586:
2580:
2576:
2572:
2568:
2567:Berstel, Jean
2564:
2563:
2558:
2550:
2546:
2541:
2537:
2532:
2528:
2523:
2519:
2513:
2510:
2505:
2501:
2497:
2495:0-521-60492-3
2491:
2487:
2483:
2477:
2476:
2469:
2466:
2462:
2458:
2454:
2450:
2446:
2442:
2438:
2433:
2430:
2427:
2421:
2418:
2412:
2409:
2403:
2400:
2397:
2393:
2387:
2384:
2381:
2375:
2372:
2369:
2368:Arden's lemma
2365:
2359:
2356:
2353:
2347:
2344:
2337:
2334:
2326:
2324:
2322:
2318:
2314:
2310:
2306:
2302:
2298:
2294:
2292:
2288:
2284:
2280:
2276:
2272:
2270:
2266:
2258:
2256:
2254:
2235:
2231:
2225:
2220:
2216:
2207:
2199:
2195:
2189:
2186:
2183:
2179:
2174:
2170:
2167:
2164:
2158:
2150:
2146:
2138:
2137:
2136:
2134:
2130:
2129:zeta function
2125:
2109:
2104:
2100:
2092:
2088:
2083:
2077:
2073:
2052:
2049:
2046:
2043:
2023:
2003:
1983:
1980:
1977:
1974:
1952:
1948:
1941:
1935:
1915:
1893:
1889:
1866:
1862:
1855:
1849:
1824:
1817:
1813:
1809:
1805:
1798:
1794:
1788:
1783:
1779:
1771:
1755:
1752:
1744:
1743:Dyck language
1727:
1724:
1702:
1699:
1689:
1673:
1668:
1664:
1657:
1649:
1645:
1641:
1638:
1635:
1630:
1625:
1621:
1614:
1606:
1602:
1598:
1592:
1584:
1580:
1559:
1539:
1516:
1508:
1504:
1481:
1477:
1473:
1470:
1447:
1439:
1435:
1430:
1427:
1423:
1417:
1409:
1405:
1397:
1379:
1375:
1370:
1367:
1363:
1358:
1354:
1345:
1327:
1323:
1314:
1310:
1292:
1289:
1286:
1278:
1270:
1266:
1258:the sequence
1245:
1237:
1233:
1229:
1210:
1202:
1198:
1191:
1183:
1179:
1173:
1170:
1167:
1163:
1159:
1153:
1145:
1141:
1133:
1132:
1131:
1130:
1126:
1122:
1106:
1086:
1063:
1055:
1051:
1038:
1033:
1029:
1025:
1021:
1018:
1015:
1011:
1007:
1006:
1005:
1002:
1000:
996:
992:
991:pumping lemma
988:
984:
980:
976:
972:
963:
956:
954:
952:
948:
944:
940:
936:
932:
928:
923:
921:
897:
894:
891:
886:
882:
876:
872:
860:
856:
852:
848:
844:
843:
838:
834:
830:
826:
822:
818:
814:
806:
804:
802:
798:
792:
790:
786:
782:
778:
774:
765:
761:
757:
753:
749:
745:
741:
737:
733:
729:
725:
721:
717:
712:
708:
704:
700:
696:
691:
687:
683:
682:
681:
678:
674:
669:
665:
661:
657:
653:
649:
645:
637:
632:
628:
624:
620:
617:
613:
609:
605:
601:
597:
593:
590:
586:
582:
578:
574:
570:
566:
548:
545:
542:
533:
532:concatenation
528:
524:
519:
515:
511:
507:
504:, hence also
502:
498:
493:
489:
485:
480:
476:
472:
468:
464:
463:
462:
460:
456:
452:
444:
442:
440:
436:
432:
430:
424:
420:
416:
412:
408:
403:
401:
396:
391:
388:
386:
382:
374:
370:
366:
362:
359:
355:
351:
348:
344:
341:
337:
333:
329:
325:
321:
317:
313:
310:
306:
302:
299:
295:
291:
289:
285:
283:
279:
277:
273:
271:
267:
265:
261:
258:
254:
251:
247:
244:
243:
242:
236:
234:
232:
228:
224:
221:
216:
214:
210:
206:
202:
198:
194:
186:
184:
182:
174:
171:
167:
163:
159:
155:
151:
147:
144:
140:
136:
132:
129:
125:
121:
117:
113:
110:
109:
108:
106:
98:
96:
94:
90:
86:
82:
78:
73:
71:
67:
63:
59:
55:
51:
47:
40:
33:
19:
4049:Nested stack
4006:
3992:Context-free
3917:Context-free
3878:Unrestricted
3741:
3709:
3694:Kleene, S.C.
3654:
3648:
3639:
3606:
3598:
3572:
3566:
3557:
3522:
3518:
3512:
3503:
3491:. Retrieved
3487:
3478:
3464:
3452:. Retrieved
3448:
3439:
3430:
3403:
3399:
3367:
3354:
3345:
3317:
3310:
3298:. Retrieved
3294:
3285:
3277:
3272:
3253:
3247:
3217:(1): 13â27.
3214:
3210:
3196:
3169:
3159:
3150:
3137:
3130:
3117:
3110:
3101:
3092:
3083:
3074:
3065:
3048:
3035:
3026:
3017:
3008:
2988:
2984:
2971:
2952:
2932:
2925:
2915:
2908:
2888:
2881:
2861:
2854:
2841:
2832:
2813:
2803:
2783:
2751:
2716:
2694:
2683:
2655:
2624:
2604:
2570:
2539:
2535:
2530:
2526:
2521:
2517:
2512:
2481:
2473:
2468:
2460:
2456:
2452:
2448:
2444:
2440:
2436:
2432:
2420:
2411:
2402:
2386:
2374:
2358:
2346:
2316:
2295:
2291:power series
2275:Rational set
2273:
2262:
2250:
2132:
2128:
2126:
1690:
1394:and complex
1235:
1227:
1225:
1124:
1042:
1030:but not the
1026:) including
1012:that is the
1003:
982:
978:
975:context-free
968:
946:
938:
934:
926:
924:
919:
854:
850:
846:
841:
836:
831:(O(1)), the
824:
820:
810:
793:
788:
784:
780:
770:
763:
759:
755:
751:
743:
739:
731:
727:
719:
715:
710:
706:
698:
694:
689:
685:
676:
672:
667:
663:
659:
655:
647:
643:
641:
630:
626:
622:
615:
611:
607:
603:
599:
595:
591:
579:operations:
568:
526:
522:
513:
509:
500:
491:
487:
484:intersection
478:
474:
458:
454:
448:
438:
434:
426:
422:
419:Noam Chomsky
414:
410:
406:
404:
399:
394:
392:
389:
384:
380:
378:
372:
353:
349:
342:
338:of a finite
335:
331:
327:
323:
319:
311:
240:
226:
222:
219:
217:
212:
208:
204:
200:
196:
193:empty string
190:
178:
169:
165:
164:(union) and
161:
157:
153:
149:
138:
134:
127:
119:
115:
102:
80:
74:
57:
53:
43:
4058:restricted
2362:2. â 1. by
2350:1. â 2. by
1496:the number
1396:polynomials
1032:Kleene star
859:palindromes
827:and equals
773:NP-complete
735:= {} ?
723:= {} ?
565:Kleene star
358:free monoid
143:Kleene star
4131:Categories
3677:1188.68177
3631:0816.68086
3549:0797.68092
3422:0675.68034
2966:Here: p.46
2862:Algorithms
2675:1169.68300
2643:0487.68064
2613:0317.94045
2593:1250.68007
2559:References
2504:0489.68046
2265:Ï-automata
1346:constants
747:= ÎŁ ?
497:complement
371:accepting
305:recognized
126:language {
87:). In the
4012:Star-free
3966:Positive
3956:Decidable
3891:Positive
3815:Languages
3748:Class REG
3527:CiteSeerX
2516:Check if
2366:or using
2287:Eilenberg
2187:≥
2180:∑
2171:
2147:ζ
2101:λ
1981:−
1949:λ
1890:λ
1863:λ
1825:π
1789:∼
1665:λ
1639:⋯
1622:λ
1474:≥
1428:…
1376:λ
1368:…
1355:λ
1315:constant
1290:≥
1171:≥
1164:∑
898:∈
600:arbitrary
546:∘
423:"regular"
407:"regular"
356:from the
124:singleton
114:For each
3810:Grammars
3493:10 April
3454:10 April
3337:53007120
3300:10 April
3239:14677270
2653:(1997).
2623:(1981).
2603:(1974).
2459:for all
1728:′
1703:′
989:and the
783:, with "
754:â ÎŁ, is
589:quotient
512:−
345:under a
316:preimage
187:Examples
105:alphabet
4033:Decider
4007:Regular
3974:Indexed
3932:Regular
3899:Indexed
3231:0738749
2545:NP-hard
2313:Boolean
1344:complex
1313:integer
1127:is the
1119:. The
851:REGULAR
837:REGULAR
821:REGULAR
767: ?
702: ?
587:, like
561:
535:
60:) is a
4085:Finite
4017:Finite
3862:Type-3
3853:Type-2
3835:Type-1
3829:Type-0
3724:
3675:
3665:
3629:
3619:
3589:
3581:
3547:
3529:
3420:
3374:
3335:
3325:
3260:
3237:
3229:
3184:
2940:
2896:
2869:
2820:
2791:
2759:
2725:
2702:
2673:
2663:
2641:
2631:
2611:
2591:
2581:
2502:
2492:
2396:latter
1208:
981:'s as
829:DSPACE
815:, the
563:, and
495:, and
451:closed
400:define
352:: ÎŁ â
340:monoid
322:â ÎŁ |
303:it is
4043:PTIME
3702:RM704
3364:(PDF)
3235:S2CID
3142:(PDF)
3122:(PDF)
2981:(PDF)
2962:(PDF)
2338:Notes
1230:is a
1014:union
652:above
471:union
259:(DFA)
252:(NFA)
231:below
118:â ÎŁ (
3790:and
3722:ISBN
3663:ISBN
3617:ISBN
3587:ISBN
3579:ISBN
3495:2018
3456:2018
3372:ISBN
3333:OCLC
3323:ISBN
3302:2018
3258:ISBN
3182:ISBN
2938:ISBN
2894:ISBN
2867:ISBN
2818:ISBN
2789:ISBN
2757:ISBN
2723:ISBN
2700:ISBN
2661:ISBN
2629:ISBN
2579:ISBN
2490:ISBN
2307:and
2279:free
2255:is.
2127:The
1123:for
1043:Let
671:and
658:and
646:and
577:trio
575:the
465:the
457:and
330:) â
215:'s.
179:See
152:and
52:, a
48:and
3714:doi
3673:Zbl
3627:Zbl
3545:Zbl
3537:doi
3523:321
3418:Zbl
3408:doi
3219:doi
3174:doi
3053:doi
2993:doi
2671:Zbl
2639:Zbl
2609:Zbl
2589:Zbl
2500:Zbl
2271:).
2168:exp
2135:is
1572:is
1552:in
1307:is
1234:if
1099:in
927:not
825:REG
823:or
811:In
801:S2S
148:If
141:* (
133:If
44:In
4133::
3786::
3746::
3720:.
3671:.
3625:.
3615:.
3543:.
3535:.
3521:.
3486:.
3447:.
3416:.
3404:66
3402:.
3398:.
3386:^
3331:.
3293:.
3233:.
3227:MR
3225:.
3215:17
3213:.
3205:;
3180:.
3168:.
3043:;
2987:.
2983:.
2771:^
2741:^
2669:.
2637:.
2587:.
2577:.
2534:=
2525:â©
2498:.
2488:.
2463:âÎŁ
2453:vw
2445:uw
2323:.
2124:.
1688:.
1342:,
1001:.
953:.
922:.
920:AC
855:AC
847:AC
842:AC
839:â
803:.
789:AA
758:â
714:â©
693:â
610:/
594:/
530:,
525:âȘ
490:â©
482:,
477:âȘ
469::
441:.
417:.
375:.)
233:.
225:|
199:,
168:âą
160:âȘ
95:.
3978:â
3936:â
3903:â
3868:â
3865:â
3859:â
3856:â
3850:â
3847:â
3844:â
3841:â
3838:â
3832:â
3776:e
3769:t
3762:v
3730:.
3716::
3704:.
3679:.
3633:.
3613:8
3551:.
3539::
3497:.
3472:.
3458:.
3424:.
3410::
3380:.
3339:.
3304:.
3266:.
3241:.
3221::
3190:.
3176::
3059:.
3055::
3001:.
2995::
2989:2
2946:.
2902:.
2875:.
2826:.
2797:.
2765:.
2731:.
2708:.
2677:.
2645:.
2615:.
2595:.
2540:A
2536:L
2531:B
2527:L
2522:A
2518:L
2506:.
2461:w
2457:L
2455:â
2449:L
2447:â
2441:v
2439:~
2437:u
2236:.
2232:)
2226:n
2221:n
2217:z
2211:)
2208:n
2205:(
2200:L
2196:s
2190:0
2184:n
2175:(
2165:=
2162:)
2159:z
2156:(
2151:L
2133:L
2110:m
2105:a
2093:a
2089:p
2084:m
2078:a
2074:C
2053:a
2050:+
2047:m
2044:d
2024:a
2004:d
1984:2
1978:,
1975:2
1953:n
1945:)
1942:n
1939:(
1936:p
1916:n
1894:i
1867:n
1859:)
1856:n
1853:(
1850:p
1818:2
1814:/
1810:3
1806:n
1799:n
1795:4
1784:n
1780:C
1756:n
1753:2
1725:L
1700:L
1674:n
1669:k
1661:)
1658:n
1655:(
1650:k
1646:p
1642:+
1636:+
1631:n
1626:1
1618:)
1615:n
1612:(
1607:1
1603:p
1599:=
1596:)
1593:n
1590:(
1585:L
1581:s
1560:L
1540:n
1520:)
1517:n
1514:(
1509:L
1505:s
1482:0
1478:n
1471:n
1451:)
1448:x
1445:(
1440:k
1436:p
1431:,
1424:,
1421:)
1418:x
1415:(
1410:1
1406:p
1380:k
1371:,
1364:,
1359:1
1328:0
1324:n
1293:0
1287:n
1283:)
1279:n
1276:(
1271:L
1267:s
1246:L
1236:L
1228:L
1211:.
1203:n
1199:z
1195:)
1192:n
1189:(
1184:L
1180:s
1174:0
1168:n
1160:=
1157:)
1154:z
1151:(
1146:L
1142:S
1125:L
1107:L
1087:n
1067:)
1064:n
1061:(
1056:L
1052:s
983:b
979:a
947:n
943:o
939:n
935:n
931:Ω
906:}
902:N
895:n
892::
887:n
883:1
877:n
873:0
869:{
785:A
764:B
760:L
756:a
752:a
744:A
740:L
732:A
728:L
720:B
716:L
711:A
707:L
699:B
695:L
690:A
686:L
677:B
673:L
668:A
664:L
660:B
656:A
648:B
644:A
631:L
627:L
623:L
618:.
616:K
612:K
608:L
604:L
596:L
592:K
572:.
569:L
549:L
543:K
527:L
523:K
517:.
514:L
510:K
501:L
492:L
488:K
479:L
475:K
459:L
455:K
431:"
427:"
385:M
381:M
373:L
354:M
350:f
343:M
336:S
332:S
328:w
326:(
324:f
320:w
318:{
312:M
300:)
296:(
227:n
223:b
220:a
213:b
209:a
205:a
201:b
197:a
170:B
166:A
162:B
158:A
154:B
150:A
139:A
135:A
128:a
120:a
116:a
41:.
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.