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