8173:Δ to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in". If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.
3262:ε. A transition without consuming an input symbol is called an ε-transition and is represented in state diagrams by an arrow labeled "ε". ε-transitions provide a convenient way of modeling systems whose current states are not precisely known: i.e., if we are modeling a system and it is not clear whether the current state (after processing some input string) should be q or q', then we can add an ε-transition between these two states, thus putting the automaton in both states simultaneously.
31:
1992:
7925:
5126:
2038:
2022:
8260:−1 copies of the machine. Each will enter a separate state. If, upon consuming the last input symbol, at least one copy of the NFA is in the accepting state, the NFA will accept. (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)
8340:
NFAs and DFAs are equivalent in that if a language is recognized by an NFA, it is also recognized by a DFA and vice versa. The establishment of such equivalence is important and useful. It is useful because constructing an NFA to recognize a given language is sometimes much easier than constructing
184:
in the name of an NFA. For each input symbol, the NFA transitions to a new state until all input symbols have been consumed. In each step, the automaton nondeterministically "chooses" one of the applicable transitions. If there exists at least one "lucky run", i.e. some sequence of choices leading to
8263:
Explicitly propagate tokens through the transition structure of the NFA and match whenever a token reaches the final state. This is sometimes useful when the NFA should encode additional context about the events that triggered the transition. (For an implementation that uses this technique to keep
188:
In the second way, the NFA consumes a string of input symbols, one by one. In each step, whenever two or more transitions are applicable, it "clones" itself into appropriately many copies, each one following a different transition. If no transition is applicable, the current copy is in a dead end,
6097:
3245:
This result shows that NFAs, despite their additional flexibility, are unable to recognize languages that cannot be recognized by some DFA. It is also important in practice for converting easier-to-construct NFAs into more efficiently executable DFAs. However, if the NFA has
7166:
1979:, which is not necessary. Sometimes, NFAs are defined with a set of initial states. There is an easy construction that translates an NFA with multiple initial states to an NFA with a single initial state, which provides a convenient notation.
5327:
1743:
3467:
2692:
7909:
3127:
4675:
2935:
4396:
1547:
8644:. In Proceedings of the 20th Annual ACM SIGPLAN Conference on Object Oriented Programming, Systems, Languages, and Applications (San Diego, CA, USA, October 16–20, 2005). OOPSLA '05. ACM, New York, NY, 345-364.
8218:
the results of the transition function applied to all current states to get the set of next states; if ε-moves are allowed, include all states reachable by such a move (ε-closure). Each step requires at most
8187:(DFA) can be found that accepts the same language. Therefore, it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the
5974:
7003:
6654:
6525:
394:
5982:
5043:
1482:
5776:
185:
an accepting state after completely consuming the input, it is accepted. Otherwise, i.e. if no choice sequence at all can consume all the input and lead to an accepting state, the input is rejected.
3016:
3943:
2830:
6721:
6171:
2180:
4199:
1013:
4456:
7042:
5893:
2749:
1607:
1788:
630:
7290:
5160:
be a NFA-ε, with a binary alphabet, that determines if the input contains an even number of 0s or an even number of 1s. Note that 0 occurrences is an even number of occurrences as well.
3333:
272:
7640:
7416:
7243:
876:
8227:
is the number of states of the NFA. On the consumption of the last input symbol, if one of the current states is a final state, the machine accepts the string. A string of length
7531:
7339:
768:
7037:
6551:
6408:
5166:
7747:
6757:
4331:
3610:
535:
7706:
6881:
4875:
4737:
4269:
1837:
6789:
5657:
5611:
3844:
1057:
7789:
6353:
3258:
Nondeterministic finite automaton with ε-moves (NFA-ε) is a further generalization to NFA. In this kind of automaton, the transition function is additionally defined on the
8341:
a DFA for that language. It is important because NFAs can be used to reduce the complexity of the mathematical work required to establish many important properties in the
6910:
6226:
4953:
4766:
7186:
4139:
3975:
3573:
2414:
498:
7482:
6253:
938:
8754:
3512:
2372:
2351:
1091:
438:
3792:
3654:
1627:
6817:
6305:
6433:
6373:
6325:
5347:
4704:
4485:
4227:
4010:
3880:
3757:
3393:
2307:
2200:
1165:
679:
349:
326:
7670:
7584:
7446:
6197:
4295:
3688:
5093:
3153:
2490:
since one state sequence satisfies the above definition; it does not matter that other sequences fail to do so. The picture can be interpreted in a couple of ways:
2274:
1944:
1276:
1125:
6848:
4042:
3717:
1396:
659:
8794:
7554:
6578:
5116:
4556:
3219:
can be reached after consuming the initial "1", this does not mean that the input "10" is accepted; rather, it means that an input string "1" would be accepted.
7359:
6277:
5816:
5796:
5677:
5561:
5158:
5066:
4976:
4915:
4895:
4833:
4813:
4793:
4533:
4505:
4113:
4093:
4070:
3737:
3634:
3534:
3364:
3217:
3197:
3177:
2571:
2539:
2516:
2488:
2454:
2434:
2330:
2247:
2094:
1964:
1917:
1897:
1877:
1857:
1421:
1367:
1340:
1316:
1296:
1245:
1225:
1205:
1185:
1145:
896:
811:
788:
699:
559:
461:
300:
3403:
2576:
3231:(DFA) can be seen as a special kind of NFA, in which for each state and symbol, the transition function has exactly one state. Thus, it is clear that every
5826:
To show NFA-ε is equivalent to NFA, first note that NFA is a special case of NFA-ε, so it remains to show for every NFA-ε, there exists an equivalent NFA.
8562:
8448:
A choice sequence may lead into a "dead end" where no transition is applicable for the current input symbol; in this case it is considered unsuccessful.
3021:
7794:
17:
8157:
Since NFAs are equivalent to nondeterministic finite automaton with ε-moves (NFA-ε), the above closures are proved using closure properties of NFA-ε.
1634:
4564:
2835:
2541:
at a given point in time, multiple arrows emanating from a node indicate cloning, a node without emanating arrows indicating the "death" of a clone.
8633:
Allan, C., Avgustinov, P., Christensen, A. S., Hendren, L., Kuzins, S., Lhoták, O., de Moor, O., Sereni, D., Sittampalam, G., and Tibble, J. 2005.
4336:
1487:
3179:(all possible state sequences for that input are shown in the upper right picture), since there is no way to reach the only accepting state,
189:
and it "dies". If, after consuming the complete input, any of the copies is in an accept state, the input is accepted, else, it is rejected.
9406:
9114:
8191:, which may lead to an exponential rise in the number of necessary states. For a formal proof of the powerset construction, please see the
8655:
Meyer, A. R.; Stockmeyer, L. J. (1972-10-25). "The equivalence problem for regular expressions with squaring requires exponential space".
8787:
9301:
8367:
9340:
6092:{\displaystyle F'={\begin{cases}F\cup \{q_{0}\}&{\text{ if }}E(q_{0})\cap F\neq \{\}\\F&{\text{ otherwise }}\\\end{cases}}}
133:
is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely,
354:
9266:
8328:
6919:
6441:
4984:
3238:
Conversely, for each NFA, there is a DFA such that it recognizes the same formal language. The DFA can be constructed using the
1426:
180:
There are at least two ways to describe the behavior of an NFA, and both of them are equivalent. The first way makes use of the
9271:
9001:
8780:
5689:
7988:
can be reached by another ε-transition. Due to the ε-transitions, the composed NFA is properly nondeterministic even if both
2940:
3887:
9276:
8926:
8019:
6585:
2754:
8637:
6659:
9016:
2099:
4144:
3537:
9487:
9261:
8941:
8406:
5898:
944:
4404:
3250:
states, the resulting DFA may have up to 2 states, which sometimes makes the construction impractical for large NFAs.
137:
can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton).
9296:
9168:
8763:
8743:
8575:
8540:
8510:
8478:
6108:
5832:
2700:
1558:
1247:, it is not required that every state sequence ends in an accepting state, it is sufficient if one does. Otherwise,
9203:
9109:
9094:
2470:
All possible state sequences for the input string "1011" are shown in the lower picture. The string is accepted by
1748:
572:
8970:
8377:
3281:
220:
169:
2545:
The feasibility to read the same picture in two ways also indicates the equivalence of both above explanations.
9383:
8362:
8184:
5564:
3228:
61:
41:
9138:
Any language in each category is generated by a grammar and by an automaton in the category in the same line.
8305:
8010:
were DFAs; vice versa, constructing a DFA for the union language (even of two DFAs) is much more complicated.
103:
7248:
9388:
9243:
8987:
8912:
7591:
7367:
7194:
1550:
816:
165:
153:
7487:
7295:
711:
9467:
9193:
9084:
8166:
3373:
8772:
8346:
7161:{\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}\;\Leftarrow \;\delta ^{*}(q_{0},w)\cap F\neq \{\};}
6530:
91:, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term
9472:
9350:
9317:
9253:
8980:
8278:
for NFA, i.e., check whether the language of a given NFA is empty. To do this, we can simply perform a
8207:
Convert to the equivalent DFA. In some cases this may cause exponential blowup in the number of states.
6726:
4300:
3582:
3476:
507:
181:
130:
7675:
6853:
4838:
4709:
4232:
1800:
9482:
9378:
9322:
9223:
9177:
8905:
8170:
6765:
5616:
5570:
3797:
1018:
7752:
7008:
6002:
9518:
9477:
9281:
9213:
9057:
9052:
6886:
6378:
6202:
4920:
4742:
3344:
7711:
7171:
4118:
3948:
3552:
2384:
477:
9426:
8232:
7451:
6231:
903:
161:
145:
8293:, i.e., if there is a string that it does not accept. As a consequence, the same is true of the
3484:
2357:
2336:
1063:
410:
9068:
9006:
8931:
8324:
6554:
6330:
5350:
3762:
3639:
3398:
2203:
1612:
8176:
The set of all strings accepted by an NFA is the language the NFA accepts. This language is a
9431:
9373:
9233:
9161:
9011:
8959:
8342:
8192:
8188:
6358:
6310:
5332:
4680:
4461:
4212:
3982:
3852:
3742:
3378:
3239:
2280:
2185:
1150:
664:
334:
311:
134:
8165:
The machine starts in the specified initial state and reads in a string of symbols from its
7645:
7559:
7421:
6176:
4274:
3667:
9238:
9104:
9079:
8936:
8897:
5322:{\displaystyle M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\delta ,S_{0},\{S_{1},S_{3}\})}
5071:
3132:
2253:
1922:
1254:
1103:
57:
8214:
of all states which the NFA might currently be in. On the consumption of an input symbol,
6824:
4018:
3693:
1372:
635:
8:
9436:
8560:
8499:
6794:
6282:
8496:
7536:
6560:
6413:
5098:
4538:
3462:{\displaystyle \delta :Q\times (\Sigma \cup \{\epsilon \})\rightarrow {\mathcal {P}}(Q)}
9365:
9332:
9089:
9031:
8975:
8372:
8279:
8211:
8023:
7344:
6262:
5801:
5781:
5684:
5662:
5546:
5143:
5051:
4961:
4900:
4880:
4818:
4798:
4778:
4518:
4490:
4098:
4078:
4055:
3722:
3619:
3519:
3349:
3202:
3182:
3162:
2687:{\displaystyle \langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle }
2556:
2524:
2501:
2473:
2461:
2439:
2419:
2315:
2232:
2079:
1949:
1902:
1882:
1862:
1842:
1406:
1352:
1325:
1301:
1281:
1230:
1210:
1190:
1170:
1147:, the machine will transition from state to state according to the transition function
1130:
881:
796:
773:
684:
544:
446:
285:
149:
126:
35:
8682:
9497:
8824:
8759:
8739:
8702:
8698:
8571:
8536:
8530:
8506:
8474:
8468:
8422:
Rabin, M. O.; Scott, D. (April 1959). "Finite
Automata and Their Decision Problems".
8402:
8297:, i.e., given two NFAs, is the language of one a subset of the language of the other.
8275:
8027:
3340:
279:
125:, who also showed their equivalence to DFAs. NFAs are used in the implementation of
8606:
4271:
denotes the set of all states the automaton may have reached when starting in state
106:, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same
9492:
9462:
9416:
9218:
9154:
9073:
9026:
8993:
8839:
8694:
8660:
8431:
8350:
8177:
5680:
2498:"lucky-run" explanation, each path in the picture denotes a sequence of choices of
2457:
708:
informal explanations, there are several equivalent formal definitions of a string
118:
111:
7904:{\textstyle \delta ^{*}(q_{0},w)=\bigcup _{r\in \delta ^{*}(q,v)}E(\delta (r,a)).}
3122:{\displaystyle \delta ^{*}(p,1011)=\delta (p,1)\cup \delta (q,1)=\{p,q\}\cup \{\}}
9345:
9286:
9198:
9036:
8951:
8918:
8834:
8807:
8803:
8670:
8641:
3232:
1343:
198:
107:
53:
45:
8657:
Proceedings of the 13th Annual
Symposium on Switching and Automata Theory (SWAT)
7958:
to the start state (left colored circle) of an appropriate subautomaton —
4095:
of states of an NFA is defined as the set of states reachable from any state in
2521:
In terms of the "cloning" explanation, each vertical column shows all clones of
1738:{\displaystyle \delta ^{*}(r,xa)=\bigcup _{r'\in \delta ^{*}(r,x)}\delta (r',a)}
9398:
9291:
9047:
8829:
8811:
8634:
8151:
4670:{\textstyle \delta ^{*}(q,wa)=\bigcup _{r\in \delta ^{*}(q,w)}E(\delta (r,a)),}
2930:{\displaystyle \delta ^{*}(p,10)=\delta (p,0)\cup \delta (q,0)=\{p\}\cup \{\}}
1100:
In words, the first condition says that the machine starts in the start state
157:
9512:
9208:
9185:
9132:
8706:
5130:
1996:
4391:{\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}
2037:
1542:{\displaystyle \delta ^{*}:Q\times \Sigma ^{*}\rightarrow {\mathcal {P}}(Q)}
9411:
9228:
8015:
7954:
in the language union, the composed automaton follows an ε-transition from
3369:
3259:
306:
2697:
Concerning the second formal definition, bottom-up computation shows that
2021:
9421:
9099:
9021:
8946:
8802:
8723:
M. O. Rabin and D. Scott, "Finite
Automata and their Decision Problems",
8664:
7984:, may reach an accepting state (right colored circle); from there, state
1207:
causes the machine to halt in one of the accepting states. In order for
8435:
122:
30:
8466:
8215:
7928:
Composed NFA accepting the union of the languages of some given NFAs
3613:
2096:, with a binary alphabet, determines if the input ends with a 1. Let
538:
8282:
from the initial state and check if some final state can be reached.
1991:
8561:
John E. Hopcroft and Rajeev
Motwani and Jeffrey D. Ullman (2003).
9457:
8497:
Alfred V. Aho and John E. Hopcroft and
Jeffrey D. Ullman (1974).
8026:. They can also be used to prove that NFAs recognize exactly the
7916:
Since NFA is equivalent to DFA, NFA-ε is also equivalent to DFA.
197:
For a more elementary introduction of the formal definition, see
1127:. The second condition says that given each character of string
8317:
8286:
8018:
the following operations. These closure operations are used in
8556:
8554:
8552:
7924:
75:
reading an input symbol is required for each state transition.
9062:
5125:
3275:
3235:
that can be recognized by a DFA can be recognized by an NFA.
2553:
formal definitions, "1011" is accepted since when reading it
661:, and is defined as the set of all strings over the alphabet
214:
9131:
Each category of languages, except those marked by a , is a
4515:
Reading the empty string may drive the automaton from state
389:{\displaystyle Q\times \Sigma \rightarrow {\mathcal {P}}(Q)}
9441:
8755:
Introduction to
Automata Theory, Languages, and Computation
8564:
Introduction to
Automata Theory, Languages, and Computation
8549:
8470:
Introduction to
Automata Theory, Languages, and Computation
6085:
9146:
8758:, Addison-Wesley Publishing, Reading Massachusetts, 1979.
8492:
8490:
6998:{\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}
6520:{\displaystyle \delta '^{*}(q_{0},w)=\delta ^{*}(q_{0},w)}
5038:{\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \emptyset ,}
1477:{\displaystyle \delta ^{*}(q_{0},w)\cap F\not =\emptyset }
164:. Besides the DFAs, other known special cases of NFAs are
5771:{\displaystyle (1^{*}01^{*}0)^{*}\cup (0^{*}10^{*}1)^{*}}
95:
is used in a narrower sense, referring to an NFA that is
8592:
8264:
4209:
Similar to NFA without ε-moves, the transition function
3659:
8487:
8399:
Introduction to
Languages and the Theory of Computation
3011:{\displaystyle \delta ^{*}(p,101)=\delta (p,1)=\{p,q\}}
8462:
8460:
8458:
8456:
8454:
7797:
4567:
3938:{\displaystyle q_{i+1}\in \delta (q_{i},\varepsilon )}
3739:
by following ε-transitions in the transition function
7755:
7714:
7678:
7648:
7594:
7562:
7539:
7490:
7454:
7424:
7370:
7347:
7298:
7251:
7197:
7174:
7045:
7011:
6922:
6889:
6856:
6827:
6797:
6768:
6729:
6662:
6649:{\displaystyle \delta '^{*}(q_{0},w)\cap F'\neq \{\}}
6588:
6563:
6533:
6444:
6416:
6381:
6361:
6333:
6313:
6285:
6265:
6234:
6205:
6179:
6111:
5985:
5901:
5835:
5804:
5784:
5692:
5665:
5619:
5573:
5549:
5335:
5169:
5146:
5101:
5074:
5054:
4987:
4964:
4923:
4903:
4883:
4841:
4821:
4801:
4781:
4745:
4712:
4683:
4541:
4521:
4493:
4464:
4407:
4339:
4303:
4277:
4235:
4215:
4147:
4121:
4101:
4081:
4058:
4021:
3985:
3951:
3890:
3855:
3800:
3765:
3745:
3725:
3696:
3670:
3642:
3622:
3585:
3555:
3522:
3487:
3406:
3381:
3352:
3284:
3205:
3185:
3165:
3135:
3024:
2943:
2838:
2825:{\displaystyle \delta ^{*}(p,1)=\delta (p,1)=\{p,q\}}
2757:
2703:
2579:
2559:
2527:
2504:
2476:
2442:
2422:
2387:
2360:
2339:
2318:
2283:
2256:
2235:
2188:
2102:
2082:
1952:
1925:
1905:
1885:
1865:
1845:
1803:
1751:
1637:
1615:
1561:
1490:
1429:
1409:
1375:
1355:
1328:
1304:
1284:
1257:
1233:
1213:
1193:
1173:
1153:
1133:
1106:
1066:
1021:
947:
906:
884:
819:
799:
776:
714:
687:
667:
638:
575:
547:
510:
480:
449:
413:
357:
337:
314:
288:
223:
8635:
Adding trace matching with free variables to AspectJ
6716:{\displaystyle \delta ^{*}(q_{0},w)\cap F\neq \{\},}
4229:
of an NFA-ε can be extended to strings. Informally,
72:
determined by its source state and input symbol, and
8451:
6259:One has to distinguish the transition functions of
2175:{\displaystyle M=(\{p,q\},\{0,1\},\delta ,p,\{q\})}
1167:. The last condition says that the machine accepts
140:NFAs have been generalized in multiple ways, e.g.,
8498:
7903:
7783:
7741:
7700:
7664:
7634:
7578:
7548:
7525:
7476:
7440:
7410:
7353:
7333:
7284:
7237:
7180:
7160:
7031:
6997:
6904:
6875:
6842:
6811:
6783:
6751:
6715:
6648:
6572:
6545:
6519:
6427:
6402:
6367:
6347:
6319:
6299:
6271:
6247:
6220:
6191:
6165:
6091:
5968:
5887:
5810:
5790:
5770:
5671:
5651:
5605:
5555:
5341:
5321:
5152:
5110:
5087:
5060:
5037:
4970:
4947:
4909:
4889:
4869:
4827:
4807:
4787:
4760:
4731:
4698:
4669:
4550:
4527:
4499:
4479:
4450:
4390:
4325:
4289:
4263:
4221:
4194:{\displaystyle E(P)=\bigcup \limits _{q\in P}E(q)}
4193:
4133:
4107:
4087:
4064:
4036:
4004:
3969:
3937:
3874:
3838:
3786:
3751:
3731:
3711:
3682:
3648:
3628:
3604:
3567:
3528:
3506:
3461:
3387:
3358:
3327:
3211:
3191:
3171:
3147:
3121:
3010:
2929:
2824:
2743:
2686:
2565:
2533:
2510:
2482:
2448:
2428:
2408:
2366:
2345:
2324:
2301:
2268:
2241:
2194:
2174:
2088:
1958:
1938:
1911:
1891:
1871:
1851:
1831:
1782:
1737:
1621:
1601:
1541:
1476:
1415:
1390:
1361:
1334:
1310:
1290:
1270:
1239:
1219:
1199:
1179:
1159:
1139:
1119:
1085:
1051:
1007:
932:
890:
870:
805:
782:
762:
693:
673:
653:
624:
553:
529:
492:
455:
432:
388:
343:
320:
294:
266:
5969:{\displaystyle M'=(Q,\Sigma ,\delta ',q_{0},F'),}
3719:denote the set of states that are reachable from
1008:{\displaystyle r_{i+1}\in \delta (r_{i},a_{i+1})}
9510:
4451:{\displaystyle \delta ^{*}(q,\varepsilon )=E(q)}
8654:
8467:John E. Hopcroft and Jeffrey D. Ullman (1979).
8289:-complete to test, given an NFA, whether it is
4204:
27:Type of finite-state machine in automata theory
8528:
8501:The Design and Analysis of Computer Algorithms
8034:Union (cf. picture); that is, if the language
6166:{\displaystyle \delta '(q,a)=\delta ^{*}(q,a)}
5888:{\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F),}
2744:{\displaystyle \delta ^{*}(p,\epsilon )=\{p\}}
1839:is the set of all states reachable from state
1602:{\displaystyle \delta ^{*}(r,\epsilon )=\{r\}}
9162:
8788:
8748:(see section 1.2: Nondeterminism, pp. 47–63.)
8681:Álvarez, Carme; Jenner, Birgit (1993-01-04).
8680:
8604:
8524:
8522:
8069:can be constructed that accepts the language
5068:may drive the automaton from its start state
1783:{\displaystyle x\in \Sigma ^{*},a\in \Sigma }
625:{\displaystyle M=(Q,\Sigma ,\delta ,q_{0},F)}
142:nondeterministic finite automata with ε-moves
8590:FOLDOC Free Online Dictionary of Computing,
7276:
7263:
7152:
7149:
7100:
7097:
6707:
6704:
6643:
6640:
6065:
6062:
6024:
6011:
5646:
5620:
5600:
5574:
5313:
5287:
5262:
5250:
5244:
5179:
3434:
3428:
3159:In contrast, the string "10" is rejected by
3142:
3136:
3116:
3113:
3107:
3095:
3005:
2993:
2924:
2921:
2915:
2909:
2819:
2807:
2738:
2732:
2681:
2651:
2645:
2580:
2296:
2284:
2263:
2257:
2166:
2160:
2142:
2130:
2124:
2112:
1596:
1590:
9110:Counter-free (with aperiodic finite monoid)
8345:. For example, it is much easier to prove
8323:. In fact, this problem is complete (under
8014:The set of languages recognized by NFAs is
3328:{\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}
267:{\displaystyle (Q,\Sigma ,\delta ,q_{0},F)}
9169:
9155:
8795:
8781:
8519:
8421:
7107:
7103:
2495:
705:
8736:Introduction to the Theory of Computation
8570:. Upper Saddle River/NJ: Addison Wesley.
8532:Introduction to the Theory of Computation
8368:Two-way nondeterministic finite automaton
4958:The automaton is said to accept a string
2003:. It is not deterministic since in state
9341:Comparison of regular-expression engines
8752:John E. Hopcroft and Jeffrey D. Ullman,
8308:of determining how many words of length
8203:There are many ways to implement a NFA:
7923:
5124:
2550:
2036:
2020:
1990:
632:, its recognized language is denoted by
175:
29:
8725:IBM Journal of Research and Development
8659:. USA: IEEE Computer Society: 125–129.
8424:IBM Journal of Research and Development
7341:contains the same state, which lies in
6228:using the extended transition function
4917:to any state in the epsilon closure of
4535:to any state of the epsilon closure of
4398:can be defined recursively as follows.
4115:following ε-transitions. Formally, for
3199:, by reading the final 0 symbol. While
1899:is accepted if some accepting state in
1251:if it is impossible at all to get from
14:
9511:
9002:Linear context-free rewriting language
8683:"A very hard log-space counting class"
8396:
7285:{\displaystyle F'\setminus \{q_{0}\},}
5818:can be defined without using ε-moves.
3265:
3129:; since that set is not disjoint from
1975:The above automaton definition uses a
564:
9302:Zhu–Takaoka string matching algorithm
9150:
8927:Linear context-free rewriting systems
8776:
8335:
7919:
7635:{\displaystyle \delta '^{*}(q_{0},w)}
7411:{\displaystyle \delta '^{*}(q_{0},w)}
7238:{\displaystyle \delta '^{*}(q_{0},w)}
5821:
3660:ε-closure of a state or set of states
3222:
2436:is nondeterministic. The language of
871:{\displaystyle r_{0},r_{1},...,r_{n}}
813:is accepted if a sequence of states,
141:
89:nondeterministic finite-state machine
8256:way decision, the NFA creates up to
7526:{\displaystyle \delta ^{*}(q_{0},w)}
7334:{\displaystyle \delta ^{*}(q_{0},w)}
6791:this follows from the definition of
2694:, which satisfies conditions 1 to 3.
1919:can be reached from the start state
763:{\displaystyle w=a_{1}a_{2}...a_{n}}
192:
9267:Boyer–Moore string-search algorithm
8605:Chris Calabro (February 27, 2005).
8022:, which constructs an NFA from any
4795:may drive the automaton from state
4164:
3253:
24:
9135:of the category directly above it.
8141:can be constructed that accepts Σ\
6896:
6864:
6737:
6546:{\displaystyle w\neq \varepsilon }
6212:
5922:
5851:
5563:can be viewed as the union of two
5029:
4752:
4720:
4374:
4360:
4311:
3588:
3445:
3422:
3382:
3294:
2361:
2340:
1777:
1759:
1525:
1511:
1471:
668:
591:
513:
372:
364:
315:
233:
25:
18:Non-deterministic finite automaton
9530:
9356:Nondeterministic finite automaton
9297:Two-way string-matching algorithm
8274:One can solve in linear time the
8252:Create multiple copies. For each
8198:
8020:Thompson's construction algorithm
7260:
6752:{\displaystyle w\in \Sigma ^{*}:}
6582:Based on this, one can show that
6355:and their extensions to strings,
4877:; after that, reading the symbol
4326:{\displaystyle w\in \Sigma ^{*}.}
3794:if there is a sequence of states
3605:{\displaystyle {\mathcal {P}}(Q)}
530:{\displaystyle {\mathcal {P}}(Q)}
110:. Like DFAs, NFAs only recognize
81:nondeterministic finite automaton
8535:. Boston/MA: PWS Publishing Co.
8107:can be constructed that accepts
7791:, and the same state must be in
7701:{\displaystyle q_{0}\not \in F,}
6876:{\displaystyle v\in \Sigma ^{*}}
5829:Given an NFA with epsilon moves
4870:{\displaystyle \delta ^{*}(q,w)}
4835:in the recursively computed set
4732:{\displaystyle w\in \Sigma ^{*}}
4264:{\displaystyle \delta ^{*}(q,w)}
3155:, the string "1011" is accepted.
2573:may traverse the state sequence
1970:
1832:{\displaystyle \delta ^{*}(r,x)}
1369:and this language is denoted by
1318:, it is said that the automaton
117:NFAs were introduced in 1959 by
99:a DFA, but not in this article.
8674:
8669:For a modern presentation, see
8647:
8627:
8378:Nondeterministic Turing machine
6784:{\displaystyle w=\varepsilon ,}
6410:respectively. By construction,
5652:{\displaystyle \{S_{3},S_{4}\}}
5606:{\displaystyle \{S_{1},S_{2}\}}
3839:{\displaystyle q_{1},...,q_{k}}
3274:is represented formally by a 5-
1322:the string. The set of strings
1052:{\displaystyle i=0,\ldots ,n-1}
213:is represented formally by a 5-
9272:Boyer–Moore–Horspool algorithm
9262:Apostolico–Giancarlo algorithm
8598:
8584:
8505:. Reading/MA: Addison-Wesley.
8473:. Reading/MA: Addison-Wesley.
8442:
8415:
8390:
8363:Deterministic finite automaton
8185:deterministic finite automaton
8086:Intersection; similarly, from
7895:
7892:
7880:
7874:
7866:
7854:
7827:
7808:
7784:{\displaystyle E(q_{0})\cap F}
7772:
7759:
7629:
7610:
7520:
7501:
7405:
7386:
7328:
7309:
7232:
7213:
7175:
7137:
7118:
7104:
7080:
7061:
7032:{\displaystyle F\subseteq F',}
6992:
6973:
6957:
6938:
6692:
6673:
6623:
6604:
6514:
6495:
6479:
6460:
6160:
6148:
6132:
6120:
6050:
6037:
5960:
5913:
5879:
5842:
5759:
5732:
5720:
5693:
5329:where the transition relation
5316:
5176:
5017:
4998:
4939:
4927:
4864:
4852:
4661:
4658:
4646:
4640:
4632:
4620:
4593:
4578:
4445:
4439:
4430:
4418:
4385:
4379:
4369:
4258:
4246:
4188:
4182:
4157:
4151:
4031:
4025:
3932:
3913:
3781:
3775:
3706:
3700:
3599:
3593:
3456:
3450:
3440:
3437:
3419:
3322:
3285:
3229:deterministic finite automaton
3089:
3077:
3068:
3056:
3047:
3035:
2987:
2975:
2966:
2954:
2903:
2891:
2882:
2870:
2861:
2849:
2801:
2789:
2780:
2768:
2726:
2714:
2416:contains more than one state,
2403:
2391:
2182:where the transition function
2169:
2109:
1826:
1814:
1732:
1715:
1707:
1695:
1663:
1648:
1584:
1572:
1536:
1530:
1520:
1459:
1440:
1385:
1379:
1002:
970:
648:
642:
619:
582:
524:
518:
383:
377:
367:
261:
224:
170:self-verifying finite automata
62:deterministic finite automaton
13:
1:
8717:
8268:
8160:
7749:then there exists a state in
6905:{\displaystyle a\in \Sigma .}
6403:{\displaystyle \delta '^{*},}
6221:{\displaystyle a\in \Sigma ,}
4948:{\displaystyle \delta (r,a).}
4761:{\displaystyle a\in \Sigma .}
2549:Considering the first of the
704:Loosely corresponding to the
104:subset construction algorithm
9277:Knuth–Morris–Pratt algorithm
9204:Damerau–Levenshtein distance
8699:10.1016/0304-3975(93)90252-O
8687:Theoretical Computer Science
8401:. McGraw Hill. p. 108.
7980:— which, by following
7742:{\displaystyle q_{0}\in F',}
7181:{\displaystyle \Rightarrow }
5120:
4507:denotes the epsilon closure;
4205:Extended transition function
4134:{\displaystyle P\subseteq Q}
3970:{\displaystyle 1\leq i<k}
3568:{\displaystyle F\subseteq Q}
2409:{\displaystyle \delta (p,1)}
493:{\displaystyle F\subseteq Q}
204:
7:
9468:Compressed pattern matching
9194:Approximate string matching
9176:
8731::2 (1959) pp. 115–125.
8356:
8327:) for the complexity class
7477:{\displaystyle q_{0}\in F,}
7168:we still have to show the "
6248:{\displaystyle \delta ^{*}}
5095:to some accepting state in
933:{\displaystyle r_{0}=q_{0}}
166:unambiguous finite automata
68:each of its transitions is
10:
9535:
9473:Longest common subsequence
9384:Needleman–Wunsch algorithm
9254:String-searching algorithm
9017:Deterministic context-free
8942:Deterministic context-free
8127:Negation; similarly, from
5613:and the other with states
3507:{\displaystyle q_{0}\in Q}
2367:{\displaystyle \emptyset }
2346:{\displaystyle \emptyset }
2206:(cf. upper left picture):
2019:
1989:
1982:
1086:{\displaystyle r_{n}\in F}
433:{\displaystyle q_{0}\in Q}
9483:Sequential pattern mining
9450:
9397:
9364:
9331:
9323:Commentz-Walter algorithm
9311:Multiple string searching
9310:
9252:
9244:Wagner–Fischer algorithm
9184:
9128:
9090:Nondeterministic pushdown
8818:
8231:can be processed in time
8171:state transition function
8169:. The automaton uses the
7533:also contains a state in
6348:{\displaystyle \delta ',}
3787:{\displaystyle p\in E(q)}
3649:{\displaystyle \epsilon }
2035:
1622:{\displaystyle \epsilon }
9493:String rewriting systems
9478:Longest common substring
9389:Smith–Waterman algorithm
9214:Gestalt pattern matching
8383:
8041:is accepted by some NFA
5679:can be described by the
5163:In formal notation, let
2456:can be described by the
2076:The following automaton
2007:reading a 1 can lead to
1859:by consuming the string
1629:is the empty string, and
146:finite-state transducers
9427:Generalized suffix tree
9351:Thompson's construction
8653:Historically shown in:
8529:Michael Sipser (1997).
8325:parsimonious reductions
6368:{\displaystyle \delta }
6320:{\displaystyle \delta }
5349:can be defined by this
5342:{\displaystyle \delta }
4699:{\displaystyle q\in Q,}
4480:{\displaystyle q\in Q,}
4297:and reading the string
4222:{\displaystyle \delta }
4075:The ε-closure of a set
4005:{\displaystyle q_{k}=p}
3875:{\displaystyle q_{1}=q}
3752:{\displaystyle \delta }
3388:{\displaystyle \Sigma }
2302:{\displaystyle \{p,q\}}
2202:can be defined by this
2195:{\displaystyle \delta }
2045:on input string "1011".
1160:{\displaystyle \delta }
674:{\displaystyle \Sigma }
344:{\displaystyle \delta }
321:{\displaystyle \Sigma }
131:Thompson's construction
48:has at least 16 states.
36:(0|1) 1 (0|1)
9379:Hirschberg's algorithm
9095:Deterministic pushdown
8971:Recursively enumerable
8353:using NFAs than DFAs.
8316:is intractable; it is
8304:and an integer n, the
8300:Given as input an NFA
8011:
7950:. For an input string
7905:
7785:
7743:
7702:
7666:
7665:{\displaystyle q_{0},}
7636:
7580:
7579:{\displaystyle q_{0}.}
7550:
7527:
7478:
7442:
7441:{\displaystyle q_{0},}
7412:
7355:
7335:
7286:
7239:
7182:
7162:
7033:
6999:
6906:
6877:
6844:
6813:
6785:
6753:
6717:
6650:
6574:
6547:
6521:
6435:has no ε-transitions.
6429:
6404:
6369:
6349:
6321:
6301:
6273:
6249:
6222:
6193:
6192:{\displaystyle q\in Q}
6167:
6093:
5970:
5889:
5812:
5792:
5772:
5673:
5653:
5607:
5557:
5351:state transition table
5343:
5323:
5154:
5137:
5112:
5089:
5062:
5039:
4972:
4949:
4911:
4891:
4871:
4829:
4809:
4789:
4762:
4733:
4700:
4671:
4552:
4529:
4501:
4481:
4452:
4392:
4327:
4291:
4290:{\displaystyle q\in Q}
4265:
4223:
4195:
4135:
4109:
4089:
4066:
4038:
4006:
3971:
3939:
3876:
3840:
3788:
3753:
3733:
3713:
3684:
3683:{\displaystyle q\in Q}
3656:denotes empty string.
3650:
3630:
3606:
3569:
3530:
3508:
3463:
3389:
3360:
3329:
3213:
3193:
3173:
3149:
3123:
3012:
2931:
2826:
2745:
2688:
2567:
2535:
2512:
2484:
2450:
2430:
2410:
2368:
2347:
2326:
2303:
2270:
2243:
2204:state transition table
2196:
2176:
2090:
2069:
2030:
2016:
1960:
1940:
1913:
1893:
1873:
1853:
1833:
1784:
1739:
1623:
1603:
1543:
1478:
1417:
1392:
1363:
1336:
1312:
1292:
1272:
1241:
1221:
1201:
1181:
1161:
1141:
1121:
1087:
1053:
1009:
934:
892:
872:
807:
784:
764:
695:
675:
655:
626:
555:
531:
494:
457:
434:
390:
345:
331:a transition function
322:
296:
268:
162:probabilistic automata
49:
9234:Levenshtein automaton
9224:Jaro–Winkler distance
8738:. PWS, Boston. 1997.
8397:Martin, John (2010).
8343:theory of computation
8193:Powerset construction
8189:powerset construction
7927:
7906:
7786:
7744:
7703:
7667:
7637:
7581:
7551:
7528:
7479:
7443:
7413:
7356:
7336:
7287:
7240:
7183:
7163:
7034:
7000:
6907:
6878:
6845:
6814:
6786:
6754:
6718:
6651:
6575:
6548:
6522:
6430:
6405:
6370:
6350:
6322:
6302:
6274:
6250:
6223:
6194:
6168:
6094:
6079: otherwise
5971:
5890:
5813:
5793:
5773:
5674:
5654:
5608:
5558:
5344:
5324:
5155:
5128:
5113:
5090:
5088:{\displaystyle q_{0}}
5063:
5040:
4973:
4950:
4912:
4892:
4872:
4830:
4810:
4790:
4763:
4734:
4701:
4672:
4553:
4530:
4502:
4482:
4453:
4393:
4328:
4292:
4266:
4224:
4196:
4136:
4110:
4090:
4067:
4039:
4007:
3972:
3940:
3877:
3841:
3789:
3754:
3734:
3714:
3685:
3651:
3631:
3607:
3570:
3531:
3509:
3464:
3390:
3361:
3330:
3240:powerset construction
3214:
3194:
3174:
3150:
3148:{\displaystyle \{q\}}
3124:
3013:
2932:
2827:
2746:
2689:
2568:
2536:
2513:
2485:
2451:
2431:
2411:
2369:
2348:
2327:
2304:
2271:
2269:{\displaystyle \{p\}}
2244:
2197:
2177:
2091:
2041:All possible runs of
2040:
2025:All possible runs of
2024:
1994:
1961:
1941:
1939:{\displaystyle q_{0}}
1914:
1894:
1874:
1854:
1834:
1785:
1740:
1624:
1604:
1544:
1479:
1418:
1393:
1364:
1337:
1313:
1293:
1273:
1271:{\displaystyle q_{0}}
1242:
1222:
1202:
1187:if the last input of
1182:
1162:
1142:
1122:
1120:{\displaystyle q_{0}}
1088:
1054:
1010:
935:
893:
873:
808:
785:
765:
696:
681:that are accepted by
676:
656:
627:
556:
532:
495:
458:
435:
391:
346:
323:
297:
269:
176:Informal introduction
33:
9282:Rabin–Karp algorithm
9239:Levenshtein distance
9080:Tree stack automaton
8665:10.1109/SWAT.1972.29
8593:Finite-State Machine
8223:computations, where
7795:
7753:
7712:
7676:
7646:
7592:
7560:
7537:
7488:
7452:
7422:
7368:
7345:
7296:
7249:
7245:contains a state in
7195:
7172:
7043:
7009:
6920:
6887:
6854:
6843:{\displaystyle w=va}
6825:
6795:
6766:
6727:
6660:
6586:
6561:
6531:
6442:
6414:
6379:
6359:
6331:
6311:
6283:
6263:
6232:
6203:
6177:
6109:
5983:
5899:
5833:
5802:
5782:
5690:
5663:
5617:
5571:
5547:
5333:
5167:
5144:
5099:
5072:
5052:
5048:that is, if reading
4985:
4962:
4921:
4901:
4881:
4839:
4819:
4799:
4779:
4743:
4710:
4681:
4565:
4539:
4519:
4491:
4462:
4405:
4337:
4301:
4275:
4233:
4213:
4145:
4119:
4099:
4079:
4056:
4037:{\displaystyle E(q)}
4019:
3983:
3949:
3888:
3853:
3798:
3763:
3743:
3723:
3712:{\displaystyle E(q)}
3694:
3668:
3640:
3620:
3583:
3553:
3520:
3485:
3404:
3379:
3350:
3282:
3203:
3183:
3163:
3133:
3022:
2941:
2836:
2755:
2701:
2577:
2557:
2525:
2502:
2474:
2440:
2420:
2385:
2358:
2337:
2316:
2281:
2254:
2233:
2186:
2100:
2080:
2029:on input string "10"
1977:single initial state
1950:
1923:
1903:
1883:
1863:
1843:
1801:
1749:
1635:
1613:
1559:
1488:
1427:
1407:
1391:{\displaystyle L(M)}
1373:
1353:
1326:
1302:
1282:
1255:
1231:
1211:
1191:
1171:
1151:
1131:
1104:
1064:
1019:
945:
904:
882:
817:
797:
774:
712:
685:
665:
654:{\displaystyle L(M)}
636:
573:
545:
508:
478:
447:
411:
355:
335:
312:
286:
221:
154:alternating automata
58:finite-state machine
9437:Ternary search tree
8988:range concatenation
8913:range concatenation
8607:"NFA to DFA blowup"
6812:{\displaystyle F'.}
6438:One can prove that
6300:{\displaystyle M',}
5659:. The language of
4775:Reading the string
2068:accepting state(s).
565:Recognized language
127:regular expressions
9366:Sequence alignment
9333:Regular expression
8640:2009-09-18 at the
8436:10.1147/rd.32.0114
8373:Pushdown automaton
8347:closure properties
8336:Application of NFA
8280:depth-first search
8212:set data structure
8024:regular expression
8012:
7920:Closure properties
7901:
7870:
7781:
7739:
7698:
7662:
7632:
7576:
7549:{\displaystyle F,}
7546:
7523:
7474:
7438:
7408:
7351:
7331:
7282:
7235:
7178:
7158:
7029:
6995:
6902:
6873:
6840:
6809:
6781:
6749:
6713:
6646:
6573:{\displaystyle w.}
6570:
6543:
6517:
6428:{\displaystyle M'}
6425:
6400:
6365:
6345:
6317:
6297:
6269:
6245:
6218:
6189:
6163:
6089:
6084:
5966:
5885:
5822:Equivalence to NFA
5808:
5798:using ε-moves but
5788:
5768:
5685:regular expression
5669:
5649:
5603:
5567:: one with states
5553:
5339:
5319:
5150:
5138:
5111:{\displaystyle F.}
5108:
5085:
5058:
5035:
4968:
4945:
4907:
4897:may drive it from
4887:
4867:
4825:
4805:
4785:
4758:
4729:
4696:
4667:
4636:
4551:{\displaystyle q.}
4548:
4525:
4497:
4477:
4448:
4388:
4323:
4287:
4261:
4219:
4191:
4178:
4131:
4105:
4085:
4062:
4034:
4002:
3967:
3935:
3872:
3836:
3784:
3749:
3729:
3709:
3680:
3646:
3626:
3602:
3565:
3526:
3504:
3459:
3385:
3356:
3325:
3223:Equivalence to DFA
3209:
3189:
3169:
3145:
3119:
3008:
2927:
2822:
2741:
2684:
2563:
2531:
2508:
2480:
2462:regular expression
2446:
2426:
2406:
2364:
2343:
2322:
2299:
2266:
2239:
2192:
2172:
2086:
2070:
2031:
2017:
1956:
1936:
1909:
1889:
1869:
1849:
1829:
1780:
1735:
1711:
1619:
1599:
1539:
1474:
1413:
1388:
1359:
1332:
1308:
1288:
1268:
1237:
1227:to be accepted by
1217:
1197:
1177:
1157:
1137:
1117:
1083:
1049:
1005:
930:
888:
868:
803:
780:
770:being accepted by
760:
691:
671:
651:
622:
551:
527:
490:
453:
430:
386:
341:
318:
292:
264:
135:Kleene's algorithm
50:
9506:
9505:
9498:String operations
9144:
9143:
9123:
9122:
9085:Embedded pushdown
8981:Context-sensitive
8906:Context-sensitive
8840:Abstract machines
8825:Chomsky hierarchy
8351:regular languages
8295:inclusion problem
8276:emptiness problem
8028:regular languages
7833:
7354:{\displaystyle F}
6656:if, and only if,
6557:on the length of
6272:{\displaystyle M}
6080:
6032:
5811:{\displaystyle M}
5791:{\displaystyle M}
5672:{\displaystyle M}
5556:{\displaystyle M}
5542:
5541:
5153:{\displaystyle M}
5061:{\displaystyle w}
4971:{\displaystyle w}
4910:{\displaystyle r}
4890:{\displaystyle a}
4828:{\displaystyle r}
4808:{\displaystyle q}
4788:{\displaystyle w}
4599:
4528:{\displaystyle q}
4500:{\displaystyle E}
4458:, for each state
4163:
4108:{\displaystyle P}
4088:{\displaystyle P}
4065:{\displaystyle q}
3732:{\displaystyle q}
3629:{\displaystyle Q}
3536:distinguished as
3529:{\displaystyle F}
3359:{\displaystyle Q}
3266:Formal definition
3212:{\displaystyle q}
3192:{\displaystyle q}
3172:{\displaystyle M}
2566:{\displaystyle M}
2534:{\displaystyle M}
2511:{\displaystyle M}
2483:{\displaystyle M}
2449:{\displaystyle M}
2429:{\displaystyle M}
2377:
2376:
2325:{\displaystyle q}
2242:{\displaystyle p}
2089:{\displaystyle M}
2074:
2073:
1959:{\displaystyle w}
1912:{\displaystyle F}
1892:{\displaystyle w}
1872:{\displaystyle x}
1852:{\displaystyle r}
1669:
1416:{\displaystyle w}
1362:{\displaystyle M}
1335:{\displaystyle M}
1311:{\displaystyle w}
1291:{\displaystyle F}
1240:{\displaystyle M}
1220:{\displaystyle w}
1200:{\displaystyle w}
1180:{\displaystyle w}
1140:{\displaystyle w}
891:{\displaystyle Q}
806:{\displaystyle w}
783:{\displaystyle M}
694:{\displaystyle M}
554:{\displaystyle Q}
463:distinguished as
456:{\displaystyle F}
295:{\displaystyle Q}
193:Formal definition
150:pushdown automata
112:regular languages
16:(Redirected from
9526:
9463:Pattern matching
9417:Suffix automaton
9219:Hamming distance
9171:
9164:
9157:
9148:
9147:
9139:
9136:
9100:Visibly pushdown
9074:Thread automaton
9022:Visibly pushdown
8990:
8947:Visibly pushdown
8915:
8902:(no common name)
8821:
8820:
8808:formal languages
8797:
8790:
8783:
8774:
8773:
8768:(See chapter 2.)
8734:Michael Sipser,
8711:
8710:
8678:
8672:
8668:
8651:
8645:
8631:
8625:
8624:
8622:
8620:
8611:
8602:
8596:
8588:
8582:
8581:
8569:
8558:
8547:
8546:
8526:
8517:
8516:
8504:
8494:
8485:
8484:
8464:
8449:
8446:
8440:
8439:
8419:
8413:
8412:
8394:
8312:are accepted by
8306:counting problem
8183:For every NFA a
8178:regular language
8009:
7998:
7979:
7968:
7949:
7938:
7910:
7908:
7907:
7902:
7869:
7853:
7852:
7820:
7819:
7807:
7806:
7790:
7788:
7787:
7782:
7771:
7770:
7748:
7746:
7745:
7740:
7735:
7724:
7723:
7707:
7705:
7704:
7699:
7688:
7687:
7671:
7669:
7668:
7663:
7658:
7657:
7641:
7639:
7638:
7633:
7622:
7621:
7609:
7608:
7607:
7585:
7583:
7582:
7577:
7572:
7571:
7555:
7553:
7552:
7547:
7532:
7530:
7529:
7524:
7513:
7512:
7500:
7499:
7483:
7481:
7480:
7475:
7464:
7463:
7447:
7445:
7444:
7439:
7434:
7433:
7417:
7415:
7414:
7409:
7398:
7397:
7385:
7384:
7383:
7360:
7358:
7357:
7352:
7340:
7338:
7337:
7332:
7321:
7320:
7308:
7307:
7291:
7289:
7288:
7283:
7275:
7274:
7259:
7244:
7242:
7241:
7236:
7225:
7224:
7212:
7211:
7210:
7187:
7185:
7184:
7179:
7167:
7165:
7164:
7159:
7130:
7129:
7117:
7116:
7093:
7073:
7072:
7060:
7059:
7058:
7038:
7036:
7035:
7030:
7025:
7004:
7002:
7001:
6996:
6985:
6984:
6972:
6971:
6950:
6949:
6937:
6936:
6935:
6911:
6909:
6908:
6903:
6882:
6880:
6879:
6874:
6872:
6871:
6849:
6847:
6846:
6841:
6818:
6816:
6815:
6810:
6805:
6790:
6788:
6787:
6782:
6758:
6756:
6755:
6750:
6745:
6744:
6723:for each string
6722:
6720:
6719:
6714:
6685:
6684:
6672:
6671:
6655:
6653:
6652:
6647:
6636:
6616:
6615:
6603:
6602:
6601:
6579:
6577:
6576:
6571:
6552:
6550:
6549:
6544:
6527:for each string
6526:
6524:
6523:
6518:
6507:
6506:
6494:
6493:
6472:
6471:
6459:
6458:
6457:
6434:
6432:
6431:
6426:
6424:
6409:
6407:
6406:
6401:
6396:
6395:
6394:
6374:
6372:
6371:
6366:
6354:
6352:
6351:
6346:
6341:
6326:
6324:
6323:
6318:
6306:
6304:
6303:
6298:
6293:
6278:
6276:
6275:
6270:
6254:
6252:
6251:
6246:
6244:
6243:
6227:
6225:
6224:
6219:
6199:and each symbol
6198:
6196:
6195:
6190:
6172:
6170:
6169:
6164:
6147:
6146:
6119:
6098:
6096:
6095:
6090:
6088:
6087:
6081:
6078:
6049:
6048:
6033:
6030:
6023:
6022:
5993:
5975:
5973:
5972:
5967:
5959:
5948:
5947:
5935:
5909:
5894:
5892:
5891:
5886:
5872:
5871:
5817:
5815:
5814:
5809:
5797:
5795:
5794:
5789:
5777:
5775:
5774:
5769:
5767:
5766:
5754:
5753:
5744:
5743:
5728:
5727:
5715:
5714:
5705:
5704:
5681:regular language
5678:
5676:
5675:
5670:
5658:
5656:
5655:
5650:
5645:
5644:
5632:
5631:
5612:
5610:
5609:
5604:
5599:
5598:
5586:
5585:
5562:
5560:
5559:
5554:
5356:
5355:
5348:
5346:
5345:
5340:
5328:
5326:
5325:
5320:
5312:
5311:
5299:
5298:
5283:
5282:
5243:
5242:
5230:
5229:
5217:
5216:
5204:
5203:
5191:
5190:
5159:
5157:
5156:
5151:
5117:
5115:
5114:
5109:
5094:
5092:
5091:
5086:
5084:
5083:
5067:
5065:
5064:
5059:
5044:
5042:
5041:
5036:
5010:
5009:
4997:
4996:
4977:
4975:
4974:
4969:
4954:
4952:
4951:
4946:
4916:
4914:
4913:
4908:
4896:
4894:
4893:
4888:
4876:
4874:
4873:
4868:
4851:
4850:
4834:
4832:
4831:
4826:
4814:
4812:
4811:
4806:
4794:
4792:
4791:
4786:
4767:
4765:
4764:
4759:
4739:and each symbol
4738:
4736:
4735:
4730:
4728:
4727:
4705:
4703:
4702:
4697:
4676:
4674:
4673:
4668:
4635:
4619:
4618:
4577:
4576:
4557:
4555:
4554:
4549:
4534:
4532:
4531:
4526:
4506:
4504:
4503:
4498:
4486:
4484:
4483:
4478:
4457:
4455:
4454:
4449:
4417:
4416:
4397:
4395:
4394:
4389:
4378:
4377:
4368:
4367:
4349:
4348:
4332:
4330:
4329:
4324:
4319:
4318:
4296:
4294:
4293:
4288:
4270:
4268:
4267:
4262:
4245:
4244:
4228:
4226:
4225:
4220:
4200:
4198:
4197:
4192:
4177:
4140:
4138:
4137:
4132:
4114:
4112:
4111:
4106:
4094:
4092:
4091:
4086:
4071:
4069:
4068:
4063:
4044:is known as the
4043:
4041:
4040:
4035:
4011:
4009:
4008:
4003:
3995:
3994:
3976:
3974:
3973:
3968:
3944:
3942:
3941:
3936:
3925:
3924:
3906:
3905:
3881:
3879:
3878:
3873:
3865:
3864:
3845:
3843:
3842:
3837:
3835:
3834:
3810:
3809:
3793:
3791:
3790:
3785:
3758:
3756:
3755:
3750:
3738:
3736:
3735:
3730:
3718:
3716:
3715:
3710:
3689:
3687:
3686:
3681:
3655:
3653:
3652:
3647:
3635:
3633:
3632:
3627:
3611:
3609:
3608:
3603:
3592:
3591:
3574:
3572:
3571:
3566:
3535:
3533:
3532:
3527:
3516:a set of states
3513:
3511:
3510:
3505:
3497:
3496:
3468:
3466:
3465:
3460:
3449:
3448:
3394:
3392:
3391:
3386:
3368:a finite set of
3365:
3363:
3362:
3357:
3335:, consisting of
3334:
3332:
3331:
3326:
3315:
3314:
3254:NFA with ε-moves
3218:
3216:
3215:
3210:
3198:
3196:
3195:
3190:
3178:
3176:
3175:
3170:
3154:
3152:
3151:
3146:
3128:
3126:
3125:
3120:
3034:
3033:
3017:
3015:
3014:
3009:
2953:
2952:
2936:
2934:
2933:
2928:
2848:
2847:
2831:
2829:
2828:
2823:
2767:
2766:
2750:
2748:
2747:
2742:
2713:
2712:
2693:
2691:
2690:
2685:
2644:
2643:
2631:
2630:
2618:
2617:
2605:
2604:
2592:
2591:
2572:
2570:
2569:
2564:
2540:
2538:
2537:
2532:
2517:
2515:
2514:
2509:
2494:In terms of the
2489:
2487:
2486:
2481:
2466:
2458:regular language
2455:
2453:
2452:
2447:
2435:
2433:
2432:
2427:
2415:
2413:
2412:
2407:
2373:
2371:
2370:
2365:
2352:
2350:
2349:
2344:
2331:
2329:
2328:
2323:
2308:
2306:
2305:
2300:
2275:
2273:
2272:
2267:
2248:
2246:
2245:
2240:
2211:
2210:
2201:
2199:
2198:
2193:
2181:
2179:
2178:
2173:
2095:
2093:
2092:
2087:
2065:
2058:
1987:
1986:
1965:
1963:
1962:
1957:
1945:
1943:
1942:
1937:
1935:
1934:
1918:
1916:
1915:
1910:
1898:
1896:
1895:
1890:
1878:
1876:
1875:
1870:
1858:
1856:
1855:
1850:
1838:
1836:
1835:
1830:
1813:
1812:
1789:
1787:
1786:
1781:
1767:
1766:
1744:
1742:
1741:
1736:
1725:
1710:
1694:
1693:
1681:
1647:
1646:
1628:
1626:
1625:
1620:
1608:
1606:
1605:
1600:
1571:
1570:
1548:
1546:
1545:
1540:
1529:
1528:
1519:
1518:
1500:
1499:
1483:
1481:
1480:
1475:
1452:
1451:
1439:
1438:
1422:
1420:
1419:
1414:
1397:
1395:
1394:
1389:
1368:
1366:
1365:
1360:
1341:
1339:
1338:
1333:
1317:
1315:
1314:
1309:
1297:
1295:
1294:
1289:
1278:to a state from
1277:
1275:
1274:
1269:
1267:
1266:
1246:
1244:
1243:
1238:
1226:
1224:
1223:
1218:
1206:
1204:
1203:
1198:
1186:
1184:
1183:
1178:
1166:
1164:
1163:
1158:
1146:
1144:
1143:
1138:
1126:
1124:
1123:
1118:
1116:
1115:
1092:
1090:
1089:
1084:
1076:
1075:
1058:
1056:
1055:
1050:
1014:
1012:
1011:
1006:
1001:
1000:
982:
981:
963:
962:
939:
937:
936:
931:
929:
928:
916:
915:
897:
895:
894:
889:
877:
875:
874:
869:
867:
866:
842:
841:
829:
828:
812:
810:
809:
804:
789:
787:
786:
781:
769:
767:
766:
761:
759:
758:
740:
739:
730:
729:
700:
698:
697:
692:
680:
678:
677:
672:
660:
658:
657:
652:
631:
629:
628:
623:
612:
611:
560:
558:
557:
552:
536:
534:
533:
528:
517:
516:
499:
497:
496:
491:
462:
460:
459:
454:
443:a set of states
439:
437:
436:
431:
423:
422:
395:
393:
392:
387:
376:
375:
350:
348:
347:
342:
327:
325:
324:
319:
305:a finite set of
301:
299:
298:
293:
274:, consisting of
273:
271:
270:
265:
254:
253:
119:Michael O. Rabin
21:
9534:
9533:
9529:
9528:
9527:
9525:
9524:
9523:
9519:Finite automata
9509:
9508:
9507:
9502:
9446:
9393:
9360:
9346:Regular grammar
9327:
9306:
9287:Raita algorithm
9248:
9199:Bitap algorithm
9180:
9175:
9145:
9140:
9137:
9130:
9124:
9119:
9041:
8985:
8964:
8910:
8891:
8814:
8812:formal grammars
8804:Automata theory
8801:
8720:
8715:
8714:
8679:
8675:
8652:
8648:
8642:Wayback Machine
8632:
8628:
8618:
8616:
8614:cseweb.ucsd.edu
8609:
8603:
8599:
8589:
8585:
8578:
8567:
8559:
8550:
8543:
8527:
8520:
8513:
8495:
8488:
8481:
8465:
8452:
8447:
8443:
8420:
8416:
8409:
8395:
8391:
8386:
8359:
8338:
8271:
8201:
8163:
8147:
8140:
8133:
8120:
8113:
8106:
8099:
8092:
8082:
8075:
8068:
8061:
8054:
8047:
8040:
8000:
7989:
7970:
7959:
7940:
7929:
7922:
7848:
7844:
7837:
7815:
7811:
7802:
7798:
7796:
7793:
7792:
7766:
7762:
7754:
7751:
7750:
7728:
7719:
7715:
7713:
7710:
7709:
7683:
7679:
7677:
7674:
7673:
7653:
7649:
7647:
7644:
7643:
7617:
7613:
7603:
7599:
7595:
7593:
7590:
7589:
7567:
7563:
7561:
7558:
7557:
7538:
7535:
7534:
7508:
7504:
7495:
7491:
7489:
7486:
7485:
7459:
7455:
7453:
7450:
7449:
7429:
7425:
7423:
7420:
7419:
7393:
7389:
7379:
7375:
7371:
7369:
7366:
7365:
7346:
7343:
7342:
7316:
7312:
7303:
7299:
7297:
7294:
7293:
7270:
7266:
7252:
7250:
7247:
7246:
7220:
7216:
7206:
7202:
7198:
7196:
7193:
7192:
7173:
7170:
7169:
7125:
7121:
7112:
7108:
7086:
7068:
7064:
7054:
7050:
7046:
7044:
7041:
7040:
7018:
7010:
7007:
7006:
6980:
6976:
6967:
6963:
6945:
6941:
6931:
6927:
6923:
6921:
6918:
6917:
6888:
6885:
6884:
6867:
6863:
6855:
6852:
6851:
6826:
6823:
6822:
6821:Otherwise, let
6798:
6796:
6793:
6792:
6767:
6764:
6763:
6740:
6736:
6728:
6725:
6724:
6680:
6676:
6667:
6663:
6661:
6658:
6657:
6629:
6611:
6607:
6597:
6593:
6589:
6587:
6584:
6583:
6562:
6559:
6558:
6532:
6529:
6528:
6502:
6498:
6489:
6485:
6467:
6463:
6453:
6449:
6445:
6443:
6440:
6439:
6417:
6415:
6412:
6411:
6390:
6386:
6382:
6380:
6377:
6376:
6360:
6357:
6356:
6334:
6332:
6329:
6328:
6312:
6309:
6308:
6286:
6284:
6281:
6280:
6264:
6261:
6260:
6239:
6235:
6233:
6230:
6229:
6204:
6201:
6200:
6178:
6175:
6174:
6173:for each state
6142:
6138:
6112:
6110:
6107:
6106:
6083:
6082:
6077:
6075:
6069:
6068:
6044:
6040:
6029:
6027:
6018:
6014:
5998:
5997:
5986:
5984:
5981:
5980:
5952:
5943:
5939:
5928:
5902:
5900:
5897:
5896:
5867:
5863:
5834:
5831:
5830:
5824:
5803:
5800:
5799:
5783:
5780:
5779:
5762:
5758:
5749:
5745:
5739:
5735:
5723:
5719:
5710:
5706:
5700:
5696:
5691:
5688:
5687:
5664:
5661:
5660:
5640:
5636:
5627:
5623:
5618:
5615:
5614:
5594:
5590:
5581:
5577:
5572:
5569:
5568:
5548:
5545:
5544:
5534:
5524:
5515:
5501:
5491:
5482:
5468:
5458:
5449:
5435:
5425:
5416:
5405:
5398:
5383:
5364:
5361:
5334:
5331:
5330:
5307:
5303:
5294:
5290:
5278:
5274:
5238:
5234:
5225:
5221:
5212:
5208:
5199:
5195:
5186:
5182:
5168:
5165:
5164:
5145:
5142:
5141:
5123:
5100:
5097:
5096:
5079:
5075:
5073:
5070:
5069:
5053:
5050:
5049:
5005:
5001:
4992:
4988:
4986:
4983:
4982:
4963:
4960:
4959:
4922:
4919:
4918:
4902:
4899:
4898:
4882:
4879:
4878:
4846:
4842:
4840:
4837:
4836:
4820:
4817:
4816:
4800:
4797:
4796:
4780:
4777:
4776:
4744:
4741:
4740:
4723:
4719:
4711:
4708:
4707:
4682:
4679:
4678:
4677:for each state
4614:
4610:
4603:
4572:
4568:
4566:
4563:
4562:
4540:
4537:
4536:
4520:
4517:
4516:
4492:
4489:
4488:
4463:
4460:
4459:
4412:
4408:
4406:
4403:
4402:
4373:
4372:
4363:
4359:
4344:
4340:
4338:
4335:
4334:
4314:
4310:
4302:
4299:
4298:
4276:
4273:
4272:
4240:
4236:
4234:
4231:
4230:
4214:
4211:
4210:
4207:
4167:
4146:
4143:
4142:
4120:
4117:
4116:
4100:
4097:
4096:
4080:
4077:
4076:
4057:
4054:
4053:
4046:epsilon closure
4020:
4017:
4016:
3990:
3986:
3984:
3981:
3980:
3950:
3947:
3946:
3920:
3916:
3895:
3891:
3889:
3886:
3885:
3860:
3856:
3854:
3851:
3850:
3830:
3826:
3805:
3801:
3799:
3796:
3795:
3764:
3761:
3760:
3744:
3741:
3740:
3724:
3721:
3720:
3695:
3692:
3691:
3669:
3666:
3665:
3662:
3641:
3638:
3637:
3621:
3618:
3617:
3587:
3586:
3584:
3581:
3580:
3554:
3551:
3550:
3521:
3518:
3517:
3492:
3488:
3486:
3483:
3482:
3444:
3443:
3405:
3402:
3401:
3380:
3377:
3376:
3351:
3348:
3347:
3310:
3306:
3283:
3280:
3279:
3268:
3256:
3233:formal language
3225:
3204:
3201:
3200:
3184:
3181:
3180:
3164:
3161:
3160:
3134:
3131:
3130:
3029:
3025:
3023:
3020:
3019:
2948:
2944:
2942:
2939:
2938:
2843:
2839:
2837:
2834:
2833:
2762:
2758:
2756:
2753:
2752:
2708:
2704:
2702:
2699:
2698:
2639:
2635:
2626:
2622:
2613:
2609:
2600:
2596:
2587:
2583:
2578:
2575:
2574:
2558:
2555:
2554:
2526:
2523:
2522:
2503:
2500:
2499:
2475:
2472:
2471:
2464:
2441:
2438:
2437:
2421:
2418:
2417:
2386:
2383:
2382:
2359:
2356:
2355:
2338:
2335:
2334:
2317:
2314:
2313:
2282:
2279:
2278:
2255:
2252:
2251:
2234:
2231:
2230:
2219:
2216:
2187:
2184:
2183:
2101:
2098:
2097:
2081:
2078:
2077:
2063:
2056:
2046:
1985:
1973:
1951:
1948:
1947:
1930:
1926:
1924:
1921:
1920:
1904:
1901:
1900:
1884:
1881:
1880:
1864:
1861:
1860:
1844:
1841:
1840:
1808:
1804:
1802:
1799:
1798:
1762:
1758:
1750:
1747:
1746:
1718:
1689:
1685:
1674:
1673:
1642:
1638:
1636:
1633:
1632:
1614:
1611:
1610:
1566:
1562:
1560:
1557:
1556:
1524:
1523:
1514:
1510:
1495:
1491:
1489:
1486:
1485:
1447:
1443:
1434:
1430:
1428:
1425:
1424:
1423:is accepted if
1408:
1405:
1404:
1403:Alternatively,
1374:
1371:
1370:
1354:
1351:
1350:
1342:accepts is the
1327:
1324:
1323:
1303:
1300:
1299:
1283:
1280:
1279:
1262:
1258:
1256:
1253:
1252:
1232:
1229:
1228:
1212:
1209:
1208:
1192:
1189:
1188:
1172:
1169:
1168:
1152:
1149:
1148:
1132:
1129:
1128:
1111:
1107:
1105:
1102:
1101:
1071:
1067:
1065:
1062:
1061:
1020:
1017:
1016:
990:
986:
977:
973:
952:
948:
946:
943:
942:
924:
920:
911:
907:
905:
902:
901:
883:
880:
879:
862:
858:
837:
833:
824:
820:
818:
815:
814:
798:
795:
794:
775:
772:
771:
754:
750:
735:
731:
725:
721:
713:
710:
709:
686:
683:
682:
666:
663:
662:
637:
634:
633:
607:
603:
574:
571:
570:
567:
546:
543:
542:
512:
511:
509:
506:
505:
479:
476:
475:
448:
445:
444:
418:
414:
412:
409:
408:
371:
370:
356:
353:
352:
336:
333:
332:
313:
310:
309:
287:
284:
283:
249:
245:
222:
219:
218:
207:
199:automata theory
195:
178:
108:formal language
54:automata theory
39:
28:
23:
22:
15:
12:
11:
5:
9532:
9522:
9521:
9504:
9503:
9501:
9500:
9495:
9490:
9485:
9480:
9475:
9470:
9465:
9460:
9454:
9452:
9448:
9447:
9445:
9444:
9439:
9434:
9429:
9424:
9419:
9414:
9409:
9403:
9401:
9399:Data structure
9395:
9394:
9392:
9391:
9386:
9381:
9376:
9370:
9368:
9362:
9361:
9359:
9358:
9353:
9348:
9343:
9337:
9335:
9329:
9328:
9326:
9325:
9320:
9314:
9312:
9308:
9307:
9305:
9304:
9299:
9294:
9292:Trigram search
9289:
9284:
9279:
9274:
9269:
9264:
9258:
9256:
9250:
9249:
9247:
9246:
9241:
9236:
9231:
9226:
9221:
9216:
9211:
9206:
9201:
9196:
9190:
9188:
9182:
9181:
9174:
9173:
9166:
9159:
9151:
9142:
9141:
9129:
9126:
9125:
9121:
9120:
9118:
9117:
9115:Acyclic finite
9112:
9107:
9102:
9097:
9092:
9087:
9082:
9076:
9071:
9066:
9065:Turing Machine
9060:
9058:Linear-bounded
9055:
9050:
9048:Turing machine
9044:
9042:
9040:
9039:
9034:
9029:
9024:
9019:
9014:
9009:
9007:Tree-adjoining
9004:
8999:
8996:
8991:
8983:
8978:
8973:
8967:
8965:
8963:
8962:
8957:
8954:
8949:
8944:
8939:
8934:
8932:Tree-adjoining
8929:
8924:
8921:
8916:
8908:
8903:
8900:
8894:
8892:
8890:
8889:
8886:
8883:
8880:
8877:
8874:
8871:
8868:
8865:
8862:
8859:
8856:
8853:
8850:
8846:
8843:
8842:
8837:
8832:
8827:
8819:
8816:
8815:
8800:
8799:
8792:
8785:
8777:
8771:
8770:
8750:
8732:
8719:
8716:
8713:
8712:
8673:
8646:
8626:
8597:
8583:
8576:
8548:
8541:
8518:
8511:
8486:
8479:
8450:
8441:
8430:(2): 114–125.
8414:
8408:978-0071289429
8407:
8388:
8387:
8385:
8382:
8381:
8380:
8375:
8370:
8365:
8358:
8355:
8337:
8334:
8333:
8332:
8298:
8283:
8270:
8267:
8266:
8265:
8261:
8250:
8208:
8200:
8199:Implementation
8197:
8162:
8159:
8155:
8154:
8152:Kleene closure
8149:
8145:
8138:
8131:
8125:
8122:
8118:
8111:
8104:
8097:
8090:
8084:
8080:
8073:
8066:
8062:, then an NFA
8059:
8052:
8045:
8038:
7921:
7918:
7914:
7913:
7912:
7911:
7900:
7897:
7894:
7891:
7888:
7885:
7882:
7879:
7876:
7873:
7868:
7865:
7862:
7859:
7856:
7851:
7847:
7843:
7840:
7836:
7832:
7829:
7826:
7823:
7818:
7814:
7810:
7805:
7801:
7780:
7777:
7774:
7769:
7765:
7761:
7758:
7738:
7734:
7731:
7727:
7722:
7718:
7697:
7694:
7691:
7686:
7682:
7661:
7656:
7652:
7631:
7628:
7625:
7620:
7616:
7612:
7606:
7602:
7598:
7586:
7575:
7570:
7566:
7545:
7542:
7522:
7519:
7516:
7511:
7507:
7503:
7498:
7494:
7473:
7470:
7467:
7462:
7458:
7437:
7432:
7428:
7407:
7404:
7401:
7396:
7392:
7388:
7382:
7378:
7374:
7362:
7350:
7330:
7327:
7324:
7319:
7315:
7311:
7306:
7302:
7281:
7278:
7273:
7269:
7265:
7262:
7258:
7255:
7234:
7231:
7228:
7223:
7219:
7215:
7209:
7205:
7201:
7177:
7157:
7154:
7151:
7148:
7145:
7142:
7139:
7136:
7133:
7128:
7124:
7120:
7115:
7111:
7106:
7102:
7099:
7096:
7092:
7089:
7085:
7082:
7079:
7076:
7071:
7067:
7063:
7057:
7053:
7049:
7028:
7024:
7021:
7017:
7014:
6994:
6991:
6988:
6983:
6979:
6975:
6970:
6966:
6962:
6959:
6956:
6953:
6948:
6944:
6940:
6934:
6930:
6926:
6913:
6912:
6901:
6898:
6895:
6892:
6870:
6866:
6862:
6859:
6839:
6836:
6833:
6830:
6819:
6808:
6804:
6801:
6780:
6777:
6774:
6771:
6748:
6743:
6739:
6735:
6732:
6712:
6709:
6706:
6703:
6700:
6697:
6694:
6691:
6688:
6683:
6679:
6675:
6670:
6666:
6645:
6642:
6639:
6635:
6632:
6628:
6625:
6622:
6619:
6614:
6610:
6606:
6600:
6596:
6592:
6569:
6566:
6542:
6539:
6536:
6516:
6513:
6510:
6505:
6501:
6497:
6492:
6488:
6484:
6481:
6478:
6475:
6470:
6466:
6462:
6456:
6452:
6448:
6423:
6420:
6399:
6393:
6389:
6385:
6364:
6344:
6340:
6337:
6316:
6296:
6292:
6289:
6268:
6257:
6256:
6255:defined above.
6242:
6238:
6217:
6214:
6211:
6208:
6188:
6185:
6182:
6162:
6159:
6156:
6153:
6150:
6145:
6141:
6137:
6134:
6131:
6128:
6125:
6122:
6118:
6115:
6100:
6099:
6086:
6076:
6074:
6071:
6070:
6067:
6064:
6061:
6058:
6055:
6052:
6047:
6043:
6039:
6036:
6031: if
6028:
6026:
6021:
6017:
6013:
6010:
6007:
6004:
6003:
6001:
5996:
5992:
5989:
5965:
5962:
5958:
5955:
5951:
5946:
5942:
5938:
5934:
5931:
5927:
5924:
5921:
5918:
5915:
5912:
5908:
5905:
5895:define an NFA
5884:
5881:
5878:
5875:
5870:
5866:
5862:
5859:
5856:
5853:
5850:
5847:
5844:
5841:
5838:
5823:
5820:
5807:
5787:
5765:
5761:
5757:
5752:
5748:
5742:
5738:
5734:
5731:
5726:
5722:
5718:
5713:
5709:
5703:
5699:
5695:
5683:given by this
5668:
5648:
5643:
5639:
5635:
5630:
5626:
5622:
5602:
5597:
5593:
5589:
5584:
5580:
5576:
5552:
5540:
5539:
5536:
5532:
5526:
5522:
5516:
5513:
5507:
5506:
5503:
5499:
5493:
5489:
5483:
5480:
5474:
5473:
5470:
5466:
5460:
5456:
5450:
5447:
5441:
5440:
5437:
5433:
5427:
5423:
5417:
5414:
5408:
5407:
5403:
5396:
5390:
5387:
5384:
5381:
5375:
5374:
5371:
5368:
5365:
5362:
5359:
5338:
5318:
5315:
5310:
5306:
5302:
5297:
5293:
5289:
5286:
5281:
5277:
5273:
5270:
5267:
5264:
5261:
5258:
5255:
5252:
5249:
5246:
5241:
5237:
5233:
5228:
5224:
5220:
5215:
5211:
5207:
5202:
5198:
5194:
5189:
5185:
5181:
5178:
5175:
5172:
5149:
5122:
5119:
5107:
5104:
5082:
5078:
5057:
5046:
5045:
5034:
5031:
5028:
5025:
5022:
5019:
5016:
5013:
5008:
5004:
5000:
4995:
4991:
4967:
4956:
4955:
4944:
4941:
4938:
4935:
4932:
4929:
4926:
4906:
4886:
4866:
4863:
4860:
4857:
4854:
4849:
4845:
4824:
4804:
4784:
4769:
4768:
4757:
4754:
4751:
4748:
4726:
4722:
4718:
4715:
4695:
4692:
4689:
4686:
4666:
4663:
4660:
4657:
4654:
4651:
4648:
4645:
4642:
4639:
4634:
4631:
4628:
4625:
4622:
4617:
4613:
4609:
4606:
4602:
4598:
4595:
4592:
4589:
4586:
4583:
4580:
4575:
4571:
4559:
4558:
4547:
4544:
4524:
4509:
4508:
4496:
4476:
4473:
4470:
4467:
4447:
4444:
4441:
4438:
4435:
4432:
4429:
4426:
4423:
4420:
4415:
4411:
4387:
4384:
4381:
4376:
4371:
4366:
4362:
4358:
4355:
4352:
4347:
4343:
4322:
4317:
4313:
4309:
4306:
4286:
4283:
4280:
4260:
4257:
4254:
4251:
4248:
4243:
4239:
4218:
4206:
4203:
4190:
4187:
4184:
4181:
4176:
4173:
4170:
4166:
4162:
4159:
4156:
4153:
4150:
4130:
4127:
4124:
4104:
4084:
4061:
4033:
4030:
4027:
4024:
4014:
4013:
4001:
3998:
3993:
3989:
3978:
3966:
3963:
3960:
3957:
3954:
3934:
3931:
3928:
3923:
3919:
3915:
3912:
3909:
3904:
3901:
3898:
3894:
3883:
3871:
3868:
3863:
3859:
3833:
3829:
3825:
3822:
3819:
3816:
3813:
3808:
3804:
3783:
3780:
3777:
3774:
3771:
3768:
3748:
3728:
3708:
3705:
3702:
3699:
3679:
3676:
3673:
3661:
3658:
3645:
3625:
3601:
3598:
3595:
3590:
3577:
3576:
3564:
3561:
3558:
3525:
3514:
3503:
3500:
3495:
3491:
3469:
3458:
3455:
3452:
3447:
3442:
3439:
3436:
3433:
3430:
3427:
3424:
3421:
3418:
3415:
3412:
3409:
3395:
3384:
3366:
3355:
3324:
3321:
3318:
3313:
3309:
3305:
3302:
3299:
3296:
3293:
3290:
3287:
3267:
3264:
3255:
3252:
3224:
3221:
3208:
3188:
3168:
3157:
3156:
3144:
3141:
3138:
3118:
3115:
3112:
3109:
3106:
3103:
3100:
3097:
3094:
3091:
3088:
3085:
3082:
3079:
3076:
3073:
3070:
3067:
3064:
3061:
3058:
3055:
3052:
3049:
3046:
3043:
3040:
3037:
3032:
3028:
3007:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2974:
2971:
2968:
2965:
2962:
2959:
2956:
2951:
2947:
2926:
2923:
2920:
2917:
2914:
2911:
2908:
2905:
2902:
2899:
2896:
2893:
2890:
2887:
2884:
2881:
2878:
2875:
2872:
2869:
2866:
2863:
2860:
2857:
2854:
2851:
2846:
2842:
2821:
2818:
2815:
2812:
2809:
2806:
2803:
2800:
2797:
2794:
2791:
2788:
2785:
2782:
2779:
2776:
2773:
2770:
2765:
2761:
2740:
2737:
2734:
2731:
2728:
2725:
2722:
2719:
2716:
2711:
2707:
2695:
2683:
2680:
2677:
2674:
2671:
2668:
2665:
2662:
2659:
2656:
2653:
2650:
2647:
2642:
2638:
2634:
2629:
2625:
2621:
2616:
2612:
2608:
2603:
2599:
2595:
2590:
2586:
2582:
2562:
2543:
2542:
2530:
2519:
2507:
2479:
2445:
2425:
2405:
2402:
2399:
2396:
2393:
2390:
2381:Since the set
2379:
2378:
2375:
2374:
2363:
2353:
2342:
2332:
2321:
2310:
2309:
2298:
2295:
2292:
2289:
2286:
2276:
2265:
2262:
2259:
2249:
2238:
2227:
2226:
2223:
2220:
2217:
2214:
2191:
2171:
2168:
2165:
2162:
2159:
2156:
2153:
2150:
2147:
2144:
2141:
2138:
2135:
2132:
2129:
2126:
2123:
2120:
2117:
2114:
2111:
2108:
2105:
2085:
2072:
2071:
2050:input symbol,
2033:
2032:
2018:
1984:
1981:
1972:
1969:
1968:
1967:
1955:
1933:
1929:
1908:
1888:
1868:
1848:
1828:
1825:
1822:
1819:
1816:
1811:
1807:
1794:
1793:
1792:
1791:
1779:
1776:
1773:
1770:
1765:
1761:
1757:
1754:
1734:
1731:
1728:
1724:
1721:
1717:
1714:
1709:
1706:
1703:
1700:
1697:
1692:
1688:
1684:
1680:
1677:
1672:
1668:
1665:
1662:
1659:
1656:
1653:
1650:
1645:
1641:
1630:
1618:
1598:
1595:
1592:
1589:
1586:
1583:
1580:
1577:
1574:
1569:
1565:
1538:
1535:
1532:
1527:
1522:
1517:
1513:
1509:
1506:
1503:
1498:
1494:
1473:
1470:
1467:
1464:
1461:
1458:
1455:
1450:
1446:
1442:
1437:
1433:
1412:
1400:
1399:
1387:
1384:
1381:
1378:
1358:
1331:
1307:
1287:
1265:
1261:
1236:
1216:
1196:
1176:
1156:
1136:
1114:
1110:
1097:
1096:
1095:
1094:
1082:
1079:
1074:
1070:
1059:
1048:
1045:
1042:
1039:
1036:
1033:
1030:
1027:
1024:
1004:
999:
996:
993:
989:
985:
980:
976:
972:
969:
966:
961:
958:
955:
951:
940:
927:
923:
919:
914:
910:
887:
865:
861:
857:
854:
851:
848:
845:
840:
836:
832:
827:
823:
802:
779:
757:
753:
749:
746:
743:
738:
734:
728:
724:
720:
717:
690:
670:
650:
647:
644:
641:
621:
618:
615:
610:
606:
602:
599:
596:
593:
590:
587:
584:
581:
578:
566:
563:
550:
526:
523:
520:
515:
502:
501:
489:
486:
483:
452:
441:
429:
426:
421:
417:
397:
385:
382:
379:
374:
369:
366:
363:
360:
340:
329:
317:
303:
291:
263:
260:
257:
252:
248:
244:
241:
238:
235:
232:
229:
226:
206:
203:
194:
191:
182:nondeterminism
177:
174:
77:
76:
73:
26:
9:
6:
4:
3:
2:
9531:
9520:
9517:
9516:
9514:
9499:
9496:
9494:
9491:
9489:
9486:
9484:
9481:
9479:
9476:
9474:
9471:
9469:
9466:
9464:
9461:
9459:
9456:
9455:
9453:
9449:
9443:
9440:
9438:
9435:
9433:
9430:
9428:
9425:
9423:
9420:
9418:
9415:
9413:
9410:
9408:
9405:
9404:
9402:
9400:
9396:
9390:
9387:
9385:
9382:
9380:
9377:
9375:
9372:
9371:
9369:
9367:
9363:
9357:
9354:
9352:
9349:
9347:
9344:
9342:
9339:
9338:
9336:
9334:
9330:
9324:
9321:
9319:
9316:
9315:
9313:
9309:
9303:
9300:
9298:
9295:
9293:
9290:
9288:
9285:
9283:
9280:
9278:
9275:
9273:
9270:
9268:
9265:
9263:
9260:
9259:
9257:
9255:
9251:
9245:
9242:
9240:
9237:
9235:
9232:
9230:
9227:
9225:
9222:
9220:
9217:
9215:
9212:
9210:
9209:Edit distance
9207:
9205:
9202:
9200:
9197:
9195:
9192:
9191:
9189:
9187:
9186:String metric
9183:
9179:
9172:
9167:
9165:
9160:
9158:
9153:
9152:
9149:
9134:
9133:proper subset
9127:
9116:
9113:
9111:
9108:
9106:
9103:
9101:
9098:
9096:
9093:
9091:
9088:
9086:
9083:
9081:
9077:
9075:
9072:
9070:
9067:
9064:
9061:
9059:
9056:
9054:
9051:
9049:
9046:
9045:
9043:
9038:
9035:
9033:
9030:
9028:
9025:
9023:
9020:
9018:
9015:
9013:
9010:
9008:
9005:
9003:
9000:
8997:
8995:
8992:
8989:
8984:
8982:
8979:
8977:
8974:
8972:
8969:
8968:
8966:
8961:
8960:Non-recursive
8958:
8955:
8953:
8950:
8948:
8945:
8943:
8940:
8938:
8935:
8933:
8930:
8928:
8925:
8922:
8920:
8917:
8914:
8909:
8907:
8904:
8901:
8899:
8896:
8895:
8893:
8887:
8884:
8881:
8878:
8875:
8872:
8869:
8866:
8863:
8860:
8857:
8854:
8851:
8848:
8847:
8845:
8844:
8841:
8838:
8836:
8833:
8831:
8828:
8826:
8823:
8822:
8817:
8813:
8809:
8805:
8798:
8793:
8791:
8786:
8784:
8779:
8778:
8775:
8769:
8765:
8764:0-201-02988-X
8761:
8757:
8756:
8751:
8749:
8745:
8744:0-534-94728-X
8741:
8737:
8733:
8730:
8726:
8722:
8721:
8708:
8704:
8700:
8696:
8692:
8688:
8684:
8677:
8671:
8666:
8662:
8658:
8650:
8643:
8639:
8636:
8630:
8615:
8608:
8601:
8595:
8594:
8587:
8579:
8577:0-201-44124-1
8573:
8566:
8565:
8557:
8555:
8553:
8544:
8542:0-534-94728-X
8538:
8534:
8533:
8525:
8523:
8514:
8512:0-201-00029-6
8508:
8503:
8502:
8493:
8491:
8482:
8480:0-201-02988-X
8476:
8472:
8471:
8463:
8461:
8459:
8457:
8455:
8445:
8437:
8433:
8429:
8425:
8418:
8410:
8404:
8400:
8393:
8389:
8379:
8376:
8374:
8371:
8369:
8366:
8364:
8361:
8360:
8354:
8352:
8348:
8344:
8330:
8326:
8322:
8320:
8315:
8311:
8307:
8303:
8299:
8296:
8292:
8288:
8284:
8281:
8277:
8273:
8272:
8262:
8259:
8255:
8251:
8248:
8244:
8241:), and space
8240:
8236:
8235:
8230:
8226:
8222:
8217:
8213:
8209:
8206:
8205:
8204:
8196:
8194:
8190:
8186:
8181:
8179:
8174:
8172:
8168:
8158:
8153:
8150:
8144:
8137:
8130:
8126:
8124:Concatenation
8123:
8117:
8110:
8103:
8096:
8089:
8085:
8079:
8072:
8065:
8058:
8051:
8044:
8037:
8033:
8032:
8031:
8029:
8025:
8021:
8017:
8007:
8003:
7996:
7992:
7987:
7983:
7977:
7973:
7966:
7962:
7957:
7953:
7947:
7943:
7936:
7932:
7926:
7917:
7898:
7889:
7886:
7883:
7877:
7871:
7863:
7860:
7857:
7849:
7845:
7841:
7838:
7834:
7830:
7824:
7821:
7816:
7812:
7803:
7799:
7778:
7775:
7767:
7763:
7756:
7736:
7732:
7729:
7725:
7720:
7716:
7695:
7692:
7689:
7684:
7680:
7659:
7654:
7650:
7626:
7623:
7618:
7614:
7604:
7600:
7596:
7587:
7573:
7568:
7564:
7543:
7540:
7517:
7514:
7509:
7505:
7496:
7492:
7471:
7468:
7465:
7460:
7456:
7435:
7430:
7426:
7402:
7399:
7394:
7390:
7380:
7376:
7372:
7363:
7348:
7325:
7322:
7317:
7313:
7304:
7300:
7279:
7271:
7267:
7256:
7253:
7229:
7226:
7221:
7217:
7207:
7203:
7199:
7190:
7189:
7188:" direction.
7155:
7146:
7143:
7140:
7134:
7131:
7126:
7122:
7113:
7109:
7094:
7090:
7087:
7083:
7077:
7074:
7069:
7065:
7055:
7051:
7047:
7026:
7022:
7019:
7015:
7012:
6989:
6986:
6981:
6977:
6968:
6964:
6960:
6954:
6951:
6946:
6942:
6932:
6928:
6924:
6915:
6914:
6899:
6893:
6890:
6868:
6860:
6857:
6837:
6834:
6831:
6828:
6820:
6806:
6802:
6799:
6778:
6775:
6772:
6769:
6761:
6760:
6759:
6746:
6741:
6733:
6730:
6710:
6701:
6698:
6695:
6689:
6686:
6681:
6677:
6668:
6664:
6637:
6633:
6630:
6626:
6620:
6617:
6612:
6608:
6598:
6594:
6590:
6580:
6567:
6564:
6556:
6540:
6537:
6534:
6511:
6508:
6503:
6499:
6490:
6486:
6482:
6476:
6473:
6468:
6464:
6454:
6450:
6446:
6436:
6421:
6418:
6397:
6391:
6387:
6383:
6362:
6342:
6338:
6335:
6314:
6294:
6290:
6287:
6266:
6240:
6236:
6215:
6209:
6206:
6186:
6183:
6180:
6157:
6154:
6151:
6143:
6139:
6135:
6129:
6126:
6123:
6116:
6113:
6105:
6104:
6103:
6072:
6059:
6056:
6053:
6045:
6041:
6034:
6019:
6015:
6008:
6005:
5999:
5994:
5990:
5987:
5979:
5978:
5977:
5963:
5956:
5953:
5949:
5944:
5940:
5936:
5932:
5929:
5925:
5919:
5916:
5910:
5906:
5903:
5882:
5876:
5873:
5868:
5864:
5860:
5857:
5854:
5848:
5845:
5839:
5836:
5827:
5819:
5805:
5785:
5763:
5755:
5750:
5746:
5740:
5736:
5729:
5724:
5716:
5711:
5707:
5701:
5697:
5686:
5682:
5666:
5641:
5637:
5633:
5628:
5624:
5595:
5591:
5587:
5582:
5578:
5566:
5550:
5537:
5531:
5527:
5521:
5517:
5512:
5509:
5508:
5504:
5498:
5494:
5488:
5484:
5479:
5476:
5475:
5471:
5465:
5461:
5455:
5451:
5446:
5443:
5442:
5438:
5432:
5428:
5422:
5418:
5413:
5410:
5409:
5402:
5395:
5391:
5388:
5385:
5380:
5377:
5376:
5372:
5369:
5366:
5358:
5357:
5354:
5352:
5336:
5308:
5304:
5300:
5295:
5291:
5284:
5279:
5275:
5271:
5268:
5265:
5259:
5256:
5253:
5247:
5239:
5235:
5231:
5226:
5222:
5218:
5213:
5209:
5205:
5200:
5196:
5192:
5187:
5183:
5173:
5170:
5161:
5147:
5136:
5132:
5131:state diagram
5127:
5118:
5105:
5102:
5080:
5076:
5055:
5032:
5026:
5023:
5020:
5014:
5011:
5006:
5002:
4993:
4989:
4981:
4980:
4979:
4965:
4942:
4936:
4933:
4930:
4924:
4904:
4884:
4861:
4858:
4855:
4847:
4843:
4822:
4815:to any state
4802:
4782:
4774:
4771:
4770:
4755:
4749:
4746:
4724:
4716:
4713:
4693:
4690:
4687:
4684:
4664:
4655:
4652:
4649:
4643:
4637:
4629:
4626:
4623:
4615:
4611:
4607:
4604:
4600:
4596:
4590:
4587:
4584:
4581:
4573:
4569:
4561:
4560:
4545:
4542:
4522:
4514:
4511:
4510:
4494:
4474:
4471:
4468:
4465:
4442:
4436:
4433:
4427:
4424:
4421:
4413:
4409:
4401:
4400:
4399:
4382:
4364:
4356:
4353:
4350:
4345:
4341:
4333:The function
4320:
4315:
4307:
4304:
4284:
4281:
4278:
4255:
4252:
4249:
4241:
4237:
4216:
4202:
4185:
4179:
4174:
4171:
4168:
4160:
4154:
4148:
4128:
4125:
4122:
4102:
4082:
4073:
4059:
4051:
4047:
4028:
4022:
3999:
3996:
3991:
3987:
3979:
3964:
3961:
3958:
3955:
3952:
3929:
3926:
3921:
3917:
3910:
3907:
3902:
3899:
3896:
3892:
3884:
3869:
3866:
3861:
3857:
3849:
3848:
3847:
3831:
3827:
3823:
3820:
3817:
3814:
3811:
3806:
3802:
3778:
3772:
3769:
3766:
3746:
3726:
3703:
3697:
3677:
3674:
3671:
3657:
3643:
3623:
3615:
3596:
3562:
3559:
3556:
3549:
3548:
3544:
3540:
3523:
3515:
3501:
3498:
3493:
3489:
3480:
3479:
3474:
3470:
3453:
3431:
3425:
3416:
3413:
3410:
3407:
3400:
3397:a transition
3396:
3375:
3371:
3370:input symbols
3367:
3353:
3346:
3342:
3338:
3337:
3336:
3319:
3316:
3311:
3307:
3303:
3300:
3297:
3291:
3288:
3277:
3273:
3263:
3261:
3251:
3249:
3243:
3241:
3236:
3234:
3230:
3220:
3206:
3186:
3166:
3139:
3110:
3104:
3101:
3098:
3092:
3086:
3083:
3080:
3074:
3071:
3065:
3062:
3059:
3053:
3050:
3044:
3041:
3038:
3030:
3026:
3002:
2999:
2996:
2990:
2984:
2981:
2978:
2972:
2969:
2963:
2960:
2957:
2949:
2945:
2918:
2912:
2906:
2900:
2897:
2894:
2888:
2885:
2879:
2876:
2873:
2867:
2864:
2858:
2855:
2852:
2844:
2840:
2816:
2813:
2810:
2804:
2798:
2795:
2792:
2786:
2783:
2777:
2774:
2771:
2763:
2759:
2735:
2729:
2723:
2720:
2717:
2709:
2705:
2696:
2678:
2675:
2672:
2669:
2666:
2663:
2660:
2657:
2654:
2648:
2640:
2636:
2632:
2627:
2623:
2619:
2614:
2610:
2606:
2601:
2597:
2593:
2588:
2584:
2560:
2552:
2548:
2547:
2546:
2528:
2520:
2505:
2497:
2493:
2492:
2491:
2477:
2468:
2463:
2460:given by the
2459:
2443:
2423:
2400:
2397:
2394:
2388:
2354:
2333:
2319:
2312:
2311:
2293:
2290:
2287:
2277:
2260:
2250:
2236:
2229:
2228:
2224:
2221:
2213:
2212:
2209:
2208:
2207:
2205:
2189:
2163:
2157:
2154:
2151:
2148:
2145:
2139:
2136:
2133:
2127:
2121:
2118:
2115:
2106:
2103:
2083:
2067:
2061:start state,
2060:
2053:
2049:
2044:
2039:
2034:
2028:
2023:
2014:
2010:
2006:
2002:
1998:
1997:state diagram
1993:
1988:
1980:
1978:
1971:Initial state
1953:
1946:by consuming
1931:
1927:
1906:
1886:
1879:. The string
1866:
1846:
1823:
1820:
1817:
1809:
1805:
1796:
1795:
1774:
1771:
1768:
1763:
1755:
1752:
1729:
1726:
1722:
1719:
1712:
1704:
1701:
1698:
1690:
1686:
1682:
1678:
1675:
1670:
1666:
1660:
1657:
1654:
1651:
1643:
1639:
1631:
1616:
1593:
1587:
1581:
1578:
1575:
1567:
1563:
1555:
1554:
1552:
1533:
1515:
1507:
1504:
1501:
1496:
1492:
1468:
1465:
1462:
1456:
1453:
1448:
1444:
1435:
1431:
1410:
1402:
1401:
1382:
1376:
1356:
1348:
1345:
1329:
1321:
1305:
1298:by following
1285:
1263:
1259:
1250:
1234:
1214:
1194:
1174:
1154:
1134:
1112:
1108:
1099:
1098:
1080:
1077:
1072:
1068:
1060:
1046:
1043:
1040:
1037:
1034:
1031:
1028:
1025:
1022:
997:
994:
991:
987:
983:
978:
974:
967:
964:
959:
956:
953:
949:
941:
925:
921:
917:
912:
908:
900:
899:
885:
863:
859:
855:
852:
849:
846:
843:
838:
834:
830:
825:
821:
800:
793:
792:
791:
777:
755:
751:
747:
744:
741:
736:
732:
726:
722:
718:
715:
707:
702:
688:
645:
639:
616:
613:
608:
604:
600:
597:
594:
588:
585:
579:
576:
569:Given an NFA
562:
548:
540:
521:
487:
484:
481:
474:
470:
466:
450:
442:
427:
424:
419:
415:
406:
402:
398:
380:
361:
358:
338:
330:
308:
307:input symbols
304:
289:
281:
277:
276:
275:
258:
255:
250:
246:
242:
239:
236:
230:
227:
216:
212:
202:
200:
190:
186:
183:
173:
171:
167:
163:
159:
155:
151:
147:
143:
138:
136:
132:
128:
124:
120:
115:
113:
109:
105:
100:
98:
94:
90:
86:
82:
74:
71:
67:
66:
65:
63:
59:
55:
47:
43:
37:
32:
19:
9412:Suffix array
9355:
9318:Aho–Corasick
9229:Lee distance
9069:Nested stack
9012:Context-free
8937:Context-free
8898:Unrestricted
8767:
8753:
8747:
8735:
8728:
8724:
8690:
8686:
8676:
8656:
8649:
8629:
8617:. Retrieved
8613:
8600:
8591:
8586:
8563:
8531:
8500:
8469:
8444:
8427:
8423:
8417:
8398:
8392:
8339:
8318:
8313:
8309:
8301:
8294:
8290:
8257:
8253:
8246:
8242:
8238:
8233:
8228:
8224:
8220:
8202:
8182:
8175:
8164:
8156:
8142:
8135:
8128:
8115:
8108:
8101:
8094:
8087:
8077:
8070:
8063:
8056:
8049:
8042:
8035:
8016:closed under
8013:
8005:
8001:
7994:
7990:
7985:
7981:
7975:
7971:
7964:
7960:
7955:
7951:
7945:
7941:
7934:
7930:
7915:
6581:
6437:
6258:
6101:
5828:
5825:
5778:. We define
5543:
5529:
5519:
5510:
5496:
5486:
5477:
5463:
5453:
5444:
5430:
5420:
5411:
5400:
5393:
5378:
5162:
5139:
5134:
5047:
4957:
4772:
4706:each string
4512:
4208:
4074:
4049:
4045:
4015:
3664:For a state
3663:
3612:denotes the
3578:
3546:
3542:
3538:
3477:
3472:
3271:
3269:
3260:empty string
3257:
3247:
3244:
3237:
3226:
3158:
3018:, and hence
2544:
2469:
2380:
2075:
2062:
2055:
2051:
2047:
2042:
2026:
2012:
2008:
2004:
2000:
1976:
1974:
1346:
1319:
1248:
878:, exists in
703:
568:
537:denotes the
503:
472:
468:
464:
404:
400:
210:
208:
196:
187:
179:
139:
116:
101:
96:
92:
88:
84:
80:
78:
69:
60:is called a
51:
9422:Suffix tree
9078:restricted
8693:(1): 3–30.
4773:Informally:
4513:Informally:
3372:called the
1551:recursively
1549:is defined
898:such that:
8718:References
8269:Complexity
8161:Properties
4487:and where
3846:such that
2052:node label
2048:Arc label:
1797:In words,
1347:recognized
282:of states
168:(UFA) and
158:ω-automata
123:Dana Scott
102:Using the
64:(DFA), if
9032:Star-free
8986:Positive
8976:Decidable
8911:Positive
8835:Languages
8707:0304-3975
8291:universal
8195:article.
7878:δ
7850:∗
7846:δ
7842:∈
7835:⋃
7804:∗
7800:δ
7776:∩
7726:∈
7642:contains
7605:∗
7597:δ
7497:∗
7493:δ
7466:∈
7418:contains
7381:∗
7373:δ
7305:∗
7301:δ
7261:∖
7208:∗
7200:δ
7176:⇒
7147:≠
7141:∩
7114:∗
7110:δ
7105:⇐
7095:≠
7084:∩
7056:∗
7048:δ
7016:⊆
6969:∗
6965:δ
6933:∗
6925:δ
6897:Σ
6894:∈
6869:∗
6865:Σ
6861:∈
6776:ε
6742:∗
6738:Σ
6734:∈
6702:≠
6696:∩
6669:∗
6665:δ
6638:≠
6627:∩
6599:∗
6591:δ
6555:induction
6541:ε
6538:≠
6491:∗
6487:δ
6455:∗
6447:δ
6392:∗
6384:δ
6363:δ
6336:δ
6315:δ
6241:∗
6237:δ
6213:Σ
6210:∈
6184:∈
6144:∗
6140:δ
6114:δ
6060:≠
6054:∩
6009:∪
5930:δ
5923:Σ
5858:δ
5852:Σ
5764:∗
5751:∗
5741:∗
5730:∪
5725:∗
5712:∗
5702:∗
5337:δ
5269:δ
5030:∅
5027:≠
5021:∩
4994:∗
4990:δ
4925:δ
4848:∗
4844:δ
4753:Σ
4750:∈
4725:∗
4721:Σ
4717:∈
4688:∈
4644:δ
4616:∗
4612:δ
4608:∈
4601:⋃
4574:∗
4570:δ
4469:∈
4428:ε
4414:∗
4410:δ
4370:→
4365:∗
4361:Σ
4357:×
4346:∗
4342:δ
4316:∗
4312:Σ
4308:∈
4282:∈
4242:∗
4238:δ
4217:δ
4172:∈
4165:⋃
4141:, define
4126:⊆
4050:ε-closure
3956:≤
3945:for each
3930:ε
3911:δ
3908:∈
3770:∈
3747:δ
3675:∈
3644:ϵ
3614:power set
3560:⊆
3539:accepting
3499:∈
3441:→
3432:ϵ
3426:∪
3423:Σ
3417:×
3408:δ
3383:Σ
3339:a finite
3301:δ
3295:Σ
3111:∪
3075:δ
3072:∪
3054:δ
3031:∗
3027:δ
2973:δ
2950:∗
2946:δ
2919:∪
2889:δ
2886:∪
2868:δ
2845:∗
2841:δ
2787:δ
2764:∗
2760:δ
2724:ϵ
2710:∗
2706:δ
2682:⟩
2652:⟨
2646:⟩
2581:⟨
2389:δ
2362:∅
2341:∅
2190:δ
2149:δ
2054:: state,
1810:∗
1806:δ
1778:Σ
1775:∈
1764:∗
1760:Σ
1756:∈
1713:δ
1691:∗
1687:δ
1683:∈
1671:⋃
1644:∗
1640:δ
1617:ϵ
1582:ϵ
1568:∗
1564:δ
1521:→
1516:∗
1512:Σ
1508:×
1497:∗
1493:δ
1472:∅
1463:∩
1436:∗
1432:δ
1155:δ
1078:∈
1044:−
1035:…
968:δ
965:∈
669:Σ
598:δ
592:Σ
539:power set
485:⊆
465:accepting
425:∈
368:→
365:Σ
362:×
339:δ
316:Σ
278:a finite
240:δ
234:Σ
205:Automaton
44:for that
9513:Category
8830:Grammars
8638:Archived
8357:See also
8167:alphabet
8055:by some
7733:′
7690:∉
7601:′
7377:′
7257:′
7204:′
7091:′
7052:′
7039:we have
7023:′
6929:′
6803:′
6634:′
6595:′
6451:′
6422:′
6388:′
6339:′
6291:′
6117:′
5991:′
5957:′
5933:′
5907:′
4048:, (also
3759:, i.e.,
3481:) state
3399:function
3374:alphabet
2937:, hence
2832:, hence
2751:, hence
1745:for all
1723:′
1679:′
1484:, where
1469:≠
1344:language
407:) state
351: :
172:(SVFA).
70:uniquely
46:language
34:NFA for
9488:Sorting
9458:Parsing
9178:Strings
9053:Decider
9027:Regular
8994:Indexed
8952:Regular
8919:Indexed
8619:6 March
8210:Keep a
8134:an NFA
8100:an NFA
5121:Example
3473:initial
2465:(0|1)*1
1983:Example
1320:rejects
401:initial
9105:Finite
9037:Finite
8882:Type-3
8873:Type-2
8855:Type-1
8849:Type-0
8762:
8742:
8705:
8574:
8539:
8509:
8477:
8405:
8287:PSPACE
8285:It is
7484:then
5976:where
3690:, let
3579:Here,
3547:states
3345:states
2011:or to
1609:where
1015:, for
504:Here,
473:states
160:, and
87:), or
9451:Other
9407:DAFSA
9374:BLAST
9063:PTIME
8610:(PDF)
8568:(PDF)
8384:Notes
8329:SpanL
8321:-hard
8216:unite
7556:viz.
7292:then
6916:From
6850:with
6553:, by
6307:viz.
5363:State
5360:Input
4052:) of
3977:, and
3543:final
3478:start
3276:tuple
3272:NFA-ε
2551:above
2496:above
2218:State
2215:Input
2057:green
706:above
469:final
440:, and
405:start
215:tuple
9442:Trie
9432:Rope
8810:and
8760:ISBN
8740:ISBN
8703:ISSN
8621:2023
8572:ISBN
8537:ISBN
8507:ISBN
8475:ISBN
8403:ISBN
8093:and
8048:and
7999:and
7939:and
7708:but
7672:and
7448:and
7005:and
6883:and
6375:and
6327:and
6279:and
6102:and
5565:DFAs
5140:Let
5133:for
5129:The
4978:if
3962:<
3636:and
3541:(or
3475:(or
3045:1011
1999:for
1995:The
1553:by:
1249:i.e.
467:(or
403:(or
121:and
56:, a
8695:doi
8691:107
8661:doi
8432:doi
8349:of
7969:or
7588:If
7364:If
7191:If
6762:If
5538:{}
5505:{}
5472:{}
5439:{}
5389:{}
5386:{}
3616:of
3471:an
3343:of
3341:set
3270:An
2964:101
2064:red
1349:by
541:of
399:an
280:set
211:NFA
209:An
97:not
93:NFA
85:NFA
52:In
42:DFA
9515::
8806::
8766:.
8746:.
8727:,
8701:.
8689:.
8685:.
8612:.
8551:^
8521:^
8489:^
8453:^
8426:.
8319:#P
8249:).
8239:ns
8180:.
8030:.
5747:10
5708:01
5535:}
5525:}
5502:}
5492:}
5469:}
5459:}
5436:}
5426:}
5406:}
5399:,
5373:ε
5370:1
5367:0
5353::
4201:.
4072:.
3545:)
3278:,
3242:.
3227:A
2859:10
2467:.
2225:1
2222:0
790::
701:.
561:.
471:)
217:,
201:.
156:,
152:,
148:,
144:,
129::
114:.
79:A
40:A
9170:e
9163:t
9156:v
8998:—
8956:—
8923:—
8888:—
8885:—
8879:—
8876:—
8870:—
8867:—
8864:—
8861:—
8858:—
8852:—
8796:e
8789:t
8782:v
8729:3
8709:.
8697::
8667:.
8663::
8623:.
8580:.
8545:.
8515:.
8483:.
8438:.
8434::
8428:3
8411:.
8331:.
8314:A
8310:n
8302:A
8258:n
8254:n
8247:s
8245:(
8243:O
8237:(
8234:O
8229:n
8225:s
8221:s
8148:.
8146:1
8143:L
8139:n
8136:A
8132:1
8129:A
8121:.
8119:2
8116:L
8114:∩
8112:1
8109:L
8105:i
8102:A
8098:2
8095:A
8091:1
8088:A
8083:.
8081:2
8078:L
8076:∪
8074:1
8071:L
8067:u
8064:A
8060:2
8057:A
8053:2
8050:L
8046:1
8043:A
8039:1
8036:L
8008:)
8006:t
8004:(
8002:N
7997:)
7995:s
7993:(
7991:N
7986:f
7982:w
7978:)
7976:t
7974:(
7972:N
7967:)
7965:s
7963:(
7961:N
7956:q
7952:w
7948:)
7946:t
7944:(
7942:N
7937:)
7935:s
7933:(
7931:N
7899:.
7896:)
7893:)
7890:a
7887:,
7884:r
7881:(
7875:(
7872:E
7867:)
7864:v
7861:,
7858:q
7855:(
7839:r
7831:=
7828:)
7825:w
7822:,
7817:0
7813:q
7809:(
7779:F
7773:)
7768:0
7764:q
7760:(
7757:E
7737:,
7730:F
7721:0
7717:q
7696:,
7693:F
7685:0
7681:q
7660:,
7655:0
7651:q
7630:)
7627:w
7624:,
7619:0
7615:q
7611:(
7574:.
7569:0
7565:q
7544:,
7541:F
7521:)
7518:w
7515:,
7510:0
7506:q
7502:(
7472:,
7469:F
7461:0
7457:q
7436:,
7431:0
7427:q
7406:)
7403:w
7400:,
7395:0
7391:q
7387:(
7361:.
7349:F
7329:)
7326:w
7323:,
7318:0
7314:q
7310:(
7280:,
7277:}
7272:0
7268:q
7264:{
7254:F
7233:)
7230:w
7227:,
7222:0
7218:q
7214:(
7156:;
7153:}
7150:{
7144:F
7138:)
7135:w
7132:,
7127:0
7123:q
7119:(
7101:}
7098:{
7088:F
7081:)
7078:w
7075:,
7070:0
7066:q
7062:(
7027:,
7020:F
7013:F
6993:)
6990:w
6987:,
6982:0
6978:q
6974:(
6961:=
6958:)
6955:w
6952:,
6947:0
6943:q
6939:(
6900:.
6891:a
6858:v
6838:a
6835:v
6832:=
6829:w
6807:.
6800:F
6779:,
6773:=
6770:w
6747::
6731:w
6711:,
6708:}
6705:{
6699:F
6693:)
6690:w
6687:,
6682:0
6678:q
6674:(
6644:}
6641:{
6631:F
6624:)
6621:w
6618:,
6613:0
6609:q
6605:(
6568:.
6565:w
6535:w
6515:)
6512:w
6509:,
6504:0
6500:q
6496:(
6483:=
6480:)
6477:w
6474:,
6469:0
6465:q
6461:(
6419:M
6398:,
6343:,
6295:,
6288:M
6267:M
6216:,
6207:a
6187:Q
6181:q
6161:)
6158:a
6155:,
6152:q
6149:(
6136:=
6133:)
6130:a
6127:,
6124:q
6121:(
6073:F
6066:}
6063:{
6057:F
6051:)
6046:0
6042:q
6038:(
6035:E
6025:}
6020:0
6016:q
6012:{
6006:F
6000:{
5995:=
5988:F
5964:,
5961:)
5954:F
5950:,
5945:0
5941:q
5937:,
5926:,
5920:,
5917:Q
5914:(
5911:=
5904:M
5883:,
5880:)
5877:F
5874:,
5869:0
5865:q
5861:,
5855:,
5849:,
5846:Q
5843:(
5840:=
5837:M
5806:M
5786:M
5760:)
5756:1
5737:0
5733:(
5721:)
5717:0
5698:1
5694:(
5667:M
5647:}
5642:4
5638:S
5634:,
5629:3
5625:S
5621:{
5601:}
5596:2
5592:S
5588:,
5583:1
5579:S
5575:{
5551:M
5533:3
5530:S
5528:{
5523:4
5520:S
5518:{
5514:4
5511:S
5500:4
5497:S
5495:{
5490:3
5487:S
5485:{
5481:3
5478:S
5467:2
5464:S
5462:{
5457:1
5454:S
5452:{
5448:2
5445:S
5434:1
5431:S
5429:{
5424:2
5421:S
5419:{
5415:1
5412:S
5404:3
5401:S
5397:1
5394:S
5392:{
5382:0
5379:S
5317:)
5314:}
5309:3
5305:S
5301:,
5296:1
5292:S
5288:{
5285:,
5280:0
5276:S
5272:,
5266:,
5263:}
5260:1
5257:,
5254:0
5251:{
5248:,
5245:}
5240:4
5236:S
5232:,
5227:3
5223:S
5219:,
5214:2
5210:S
5206:,
5201:1
5197:S
5193:,
5188:0
5184:S
5180:{
5177:(
5174:=
5171:M
5148:M
5135:M
5106:.
5103:F
5081:0
5077:q
5056:w
5033:,
5024:F
5018:)
5015:w
5012:,
5007:0
5003:q
4999:(
4966:w
4943:.
4940:)
4937:a
4934:,
4931:r
4928:(
4905:r
4885:a
4865:)
4862:w
4859:,
4856:q
4853:(
4823:r
4803:q
4783:w
4756:.
4747:a
4714:w
4694:,
4691:Q
4685:q
4665:,
4662:)
4659:)
4656:a
4653:,
4650:r
4647:(
4641:(
4638:E
4633:)
4630:w
4627:,
4624:q
4621:(
4605:r
4597:=
4594:)
4591:a
4588:w
4585:,
4582:q
4579:(
4546:.
4543:q
4523:q
4495:E
4475:,
4472:Q
4466:q
4446:)
4443:q
4440:(
4437:E
4434:=
4431:)
4425:,
4422:q
4419:(
4386:)
4383:Q
4380:(
4375:P
4354:Q
4351::
4321:.
4305:w
4285:Q
4279:q
4259:)
4256:w
4253:,
4250:q
4247:(
4189:)
4186:q
4183:(
4180:E
4175:P
4169:q
4161:=
4158:)
4155:P
4152:(
4149:E
4129:Q
4123:P
4103:P
4083:P
4060:q
4032:)
4029:q
4026:(
4023:E
4012:.
4000:p
3997:=
3992:k
3988:q
3965:k
3959:i
3953:1
3933:)
3927:,
3922:i
3918:q
3914:(
3903:1
3900:+
3897:i
3893:q
3882:,
3870:q
3867:=
3862:1
3858:q
3832:k
3828:q
3824:,
3821:.
3818:.
3815:.
3812:,
3807:1
3803:q
3782:)
3779:q
3776:(
3773:E
3767:p
3727:q
3707:)
3704:q
3701:(
3698:E
3678:Q
3672:q
3624:Q
3600:)
3597:Q
3594:(
3589:P
3575:.
3563:Q
3557:F
3524:F
3502:Q
3494:0
3490:q
3457:)
3454:Q
3451:(
3446:P
3438:)
3435:}
3429:{
3420:(
3414:Q
3411::
3354:Q
3323:)
3320:F
3317:,
3312:0
3308:q
3304:,
3298:,
3292:,
3289:Q
3286:(
3248:n
3207:q
3187:q
3167:M
3143:}
3140:q
3137:{
3117:}
3114:{
3108:}
3105:q
3102:,
3099:p
3096:{
3093:=
3090:)
3087:1
3084:,
3081:q
3078:(
3069:)
3066:1
3063:,
3060:p
3057:(
3051:=
3048:)
3042:,
3039:p
3036:(
3006:}
3003:q
3000:,
2997:p
2994:{
2991:=
2988:)
2985:1
2982:,
2979:p
2976:(
2970:=
2967:)
2961:,
2958:p
2955:(
2925:}
2922:{
2916:}
2913:p
2910:{
2907:=
2904:)
2901:0
2898:,
2895:q
2892:(
2883:)
2880:0
2877:,
2874:p
2871:(
2865:=
2862:)
2856:,
2853:p
2850:(
2820:}
2817:q
2814:,
2811:p
2808:{
2805:=
2802:)
2799:1
2796:,
2793:p
2790:(
2784:=
2781:)
2778:1
2775:,
2772:p
2769:(
2739:}
2736:p
2733:{
2730:=
2727:)
2721:,
2718:p
2715:(
2679:q
2676:,
2673:p
2670:,
2667:p
2664:,
2661:p
2658:,
2655:p
2649:=
2641:4
2637:r
2633:,
2628:3
2624:r
2620:,
2615:2
2611:r
2607:,
2602:1
2598:r
2594:,
2589:0
2585:r
2561:M
2529:M
2518:.
2506:M
2478:M
2444:M
2424:M
2404:)
2401:1
2398:,
2395:p
2392:(
2320:q
2297:}
2294:q
2291:,
2288:p
2285:{
2264:}
2261:p
2258:{
2237:p
2170:)
2167:}
2164:q
2161:{
2158:,
2155:p
2152:,
2146:,
2143:}
2140:1
2137:,
2134:0
2131:{
2128:,
2125:}
2122:q
2119:,
2116:p
2113:{
2110:(
2107:=
2104:M
2084:M
2066::
2059::
2043:M
2027:M
2015:.
2013:q
2009:p
2005:p
2001:M
1966:.
1954:w
1932:0
1928:q
1907:F
1887:w
1867:x
1847:r
1827:)
1824:x
1821:,
1818:r
1815:(
1790:.
1772:a
1769:,
1753:x
1733:)
1730:a
1727:,
1720:r
1716:(
1708:)
1705:x
1702:,
1699:r
1696:(
1676:r
1667:=
1664:)
1661:a
1658:x
1655:,
1652:r
1649:(
1597:}
1594:r
1591:{
1588:=
1585:)
1579:,
1576:r
1573:(
1537:)
1534:Q
1531:(
1526:P
1505:Q
1502::
1466:F
1460:)
1457:w
1454:,
1449:0
1445:q
1441:(
1411:w
1398:.
1386:)
1383:M
1380:(
1377:L
1357:M
1330:M
1306:w
1286:F
1264:0
1260:q
1235:M
1215:w
1195:w
1175:w
1135:w
1113:0
1109:q
1093:.
1081:F
1073:n
1069:r
1047:1
1041:n
1038:,
1032:,
1029:0
1026:=
1023:i
1003:)
998:1
995:+
992:i
988:a
984:,
979:i
975:r
971:(
960:1
957:+
954:i
950:r
926:0
922:q
918:=
913:0
909:r
886:Q
864:n
860:r
856:,
853:.
850:.
847:.
844:,
839:1
835:r
831:,
826:0
822:r
801:w
778:M
756:n
752:a
748:.
745:.
742:.
737:2
733:a
727:1
723:a
719:=
716:w
689:M
649:)
646:M
643:(
640:L
620:)
617:F
614:,
609:0
605:q
601:,
595:,
589:,
586:Q
583:(
580:=
577:M
549:Q
525:)
522:Q
519:(
514:P
500:.
488:Q
482:F
451:F
428:Q
420:0
416:q
396:,
384:)
381:Q
378:(
373:P
359:Q
328:,
302:,
290:Q
262:)
259:F
256:,
251:0
247:q
243:,
237:,
231:,
228:Q
225:(
83:(
38:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
