514:
493:
478:
58:. It is important in theory because it establishes that NFAs, despite their additional flexibility, are unable to recognize any language 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
591:
uses the powerset construction, twice. It converts the input DFA into an NFA for the reverse language, by reversing all its arrows and exchanging the roles of initial and accepting states, converts the NFA back into a DFA using the powerset construction, and then repeats its process. Its worst-case
277:
Compute the ε-closure of the entire automaton as a preprocessing step, producing an equivalent NFA without ε-moves, then apply the regular powerset construction. This version, also discussed by
Hopcroft and Ullman, is straightforward to implement, but impractical for automata with large numbers of
484:
The initial state of the DFA constructed from this NFA is the set of all NFA states that are reachable from state 1 by ε-moves; that is, it is the set {1,2,3}. A transition from {1,2,3} by input symbol 0 must follow either the arrow from state 1 to state 2, or the arrow from state 3 to state 4.
89:
of the input. In contrast, to simulate an NFA, one needs to keep track of a set of states: all of the states that the automaton could reach after seeing the same prefix of the input, according to the nondeterministic choices made by the automaton. If, after a certain prefix of the input, a set
106:. Therefore, the sets of reachable NFA states play the same role in the NFA simulation as single DFA states play in the DFA simulation, and in fact the sets of NFA states appearing in this simulation may be re-interpreted as being states of a DFA.
465:
If NFAs are defined to allow for multiple initial states, the initial state of the corresponding DFA is the set of all initial states of the NFA, or (if the NFA also has ε-moves) the set of all states reachable from initial states by ε-moves.
446:
258:. However, many states of the resulting DFA may be useless as they may be unreachable from the initial state. An alternative version of the construction creates only the states that are actually reachable.
351:
273:
of states: the set of all states reachable from some given state using only ε-moves. Van Noord recognizes three possible ways of incorporating this closure computation in the powerset construction:
114:
The powerset construction applies most directly to an NFA that does not allow state transformations without consuming input symbols (aka: "ε-moves"). Such an automaton may be defined as a
499:
As can be seen in this example, there are five states reachable from the start state of the DFA; the remaining 11 sets in the powerset of the set of NFA states are not reachable.
592:
complexity is exponential, unlike some other known DFA minimization algorithms, but in many examples it performs more quickly than its worst-case complexity would suggest.
85:
To simulate the operation of a DFA on a given input string, one needs to keep track of a single state at any time: the state that the automaton will reach after seeing a
723:
595:
895:
Moore, Frank R. (1971). "On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata".
474:
The NFA below has four states; state 1 is initial, and states 3 and 4 are accepting. Its alphabet consists of the two symbols 0 and 1, and it has ε-moves.
62:
states, the resulting DFA may have up to 2 states, an exponentially larger number, which sometimes makes the construction impractical for large NFAs.
549:
time complexity. A simple example requiring nearly this many states is the language of strings over the alphabet {0,1} in which there are at least
17:
963:
363:
931:
1003:
768:
69:(or subset construction) to distinguish it from similar constructions for other types of automata, was first published by
537:-state NFAs such that every subset of states is reachable from the initial subset, so that the converted DFA has exactly
288:
266:
For an NFA with ε-moves (also called an ε-NFA), the construction must be modified to deal with these by computing the
859:
736:
698:
47:
489:({1,2,3},0) = {2,4}, and by the same reasoning the full DFA constructed from the NFA is as shown below.
51:
588:
269:
279:
788:
1022:
758:
246:
In the simplest version of the powerset construction, the set of all states of the DFA is the
993:
849:
728:
690:
683:
546:
165:
is the set of accepting states. The corresponding DFA has states corresponding to subsets of
31:
943:
180:, the (one-element) set of initial states. The transition function of the DFA maps a state
8:
938:. Polytechnic Press of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y. pp. 529–561.
912:
818:
800:
934:(1963). "Canonical regular expressions and minimal state graphs for definite events".
599:
999:
916:
855:
764:
732:
694:
655:
513:
152:
is the transition function (mapping a state and an input symbol to a set of states),
492:
477:
969:
904:
822:
810:
647:
631:
607:
508:
70:
939:
55:
35:
718:
678:
611:
1016:
714:
659:
973:
908:
814:
485:
Additionally, neither state 2 nor state 4 have outgoing ε-moves. Therefore,
86:
957:
876:
Lupanov, Oleg B. (1963). "A comparison of two types of finite sources".
614:
with 2 states, uses the powerset construction as part of its machinery.
805:
651:
635:
239:
of the DFA is an accepting state if and only if at least one member of
74:
851:
Complexity Theory and
Cryptology: An Introduction to Cryptocomplexity
247:
854:. Texts in Theoretical Computer Science. Springer. pp. 21–22.
441:{\displaystyle \{q'~|~\exists q\in Q',q\to _{\varepsilon }^{*}q'\}}
968:. Washington, DC, US: IEEE Computer Society. pp. 319–327.
760:
Verification of reactive systems: formal methods and algorithms
517:
NFA with 5 states (left) whose DFA (right) requires 16 states.
452:
that is considered by the algorithm, and add its elements to
115:
724:
Introduction to
Automata Theory, Languages, and Computation
357:
that is considered by the algorithm (and cache the result).
98:
the set of reachable states is a deterministic function of
94:
of states can be reached, then after the next input symbol
521:
Because the DFA states consist of sets of NFA states, an
557:
th from last of which is 1. It can be represented by an
936:
Proc. Sympos. Math. Theory of
Automata (New York, 1962)
638:(1959). "Finite automata and their decision problems".
360:
During the powerset computation, compute the ε-closure
285:
During the powerset computation, compute the ε-closure
366:
291:
789:"Treatment of epsilon moves in subset construction"
346:{\displaystyle \{q'~|~q\to _{\varepsilon }^{*}q'\}}
727:. Reading Massachusetts: Addison-Wesley. pp.
682:
525:-state NFA may be converted to a DFA with at most
440:
345:
227:, the set of all states that can be reached by an
1014:
573:-character suffix of the input; cf. picture for
27:Method for making finite automata deterministic
998:. Cambridge University Press. pp. 43–49.
835:
721:(1979). "The equivalence of DFA's and NFA's".
713:
964:Symposium on Foundations of Computer Science
491:
476:
435:
367:
340:
292:
960:(1988). "On the complexity of ω-automata".
752:
750:
748:
589:Brzozowski's algorithm for DFA minimization
930:
782:
780:
630:
460:
804:
786:
756:
685:Introduction to the Theory of Computation
995:Automata theory with modern applications
991:
745:
673:
671:
669:
512:
875:
777:
640:IBM Journal of Research and Development
65:The construction, sometimes called the
14:
1015:
888:
677:
46:is a standard method for converting a
956:
894:
847:
666:
598:, which converts a non-deterministic
254:, the set of all possible subsets of
261:
24:
985:
389:
243:is an accepting state of the NFA.
169:. The initial state of the DFA is
25:
1034:
707:
67:Rabin–Scott powerset construction
48:nondeterministic finite automaton
54:(DFA) which recognizes the same
992:Anderson, James Andrew (2006).
962:Proceedings of the 29th Annual
950:
924:
583:
109:
897:IEEE Transactions on Computers
869:
841:
829:
763:. Springer. pp. 210–212.
624:
413:
382:
318:
307:
278:ε-moves, as commonly arise in
52:deterministic finite automaton
13:
1:
617:
502:
148:is the set of input symbols,
18:Subset construction algorithm
836:Hopcroft & Ullman (1979)
606:states into a deterministic
565:-state NFA, but it requires
231:-transition from a state in
80:
7:
787:Van Noord, Gertjan (2000).
280:natural language processing
10:
1039:
506:
469:
184:(representing a subset of
161:is the initial state, and
793:Computational Linguistics
757:Schneider, Klaus (2004).
569:DFA states, one for each
448:of each subset of states
681:(1997). "Theorem 1.19".
610:or into a deterministic
974:10.1109/SFCS.1988.21948
909:10.1109/T-C.1971.223108
815:10.1162/089120100561638
461:Multiple initial states
518:
496:
481:
442:
347:
188:) and an input symbol
144:is the set of states,
516:
495:
480:
443:
348:
40:powerset construction
32:theory of computation
878:Problemy Kibernetiki
848:Rothe, Jörg (2006).
596:Safra's construction
364:
289:
426:
331:
44:subset construction
719:Ullman, Jeffrey D.
652:10.1147/rd.32.0114
529:states. For every
519:
497:
482:
438:
412:
343:
317:
1005:978-0-521-84887-9
932:Brzozowski, J. A.
903:(10): 1211–1214.
838:, pp. 26–27.
770:978-3-540-00296-3
715:Hopcroft, John E.
541:states, giving Θ(
388:
380:
313:
305:
16:(Redirected from
1030:
1009:
979:
977:
954:
948:
947:
928:
922:
920:
892:
886:
885:
873:
867:
865:
845:
839:
833:
827:
826:
808:
784:
775:
774:
754:
743:
742:
711:
705:
704:
688:
675:
664:
663:
628:
608:Muller automaton
605:
579:
572:
568:
564:
556:
553:characters, the
552:
544:
540:
536:
532:
528:
524:
509:State complexity
488:
455:
451:
447:
445:
444:
439:
434:
425:
420:
405:
386:
385:
378:
377:
356:
352:
350:
349:
344:
339:
330:
325:
311:
310:
303:
302:
262:NFA with ε-moves
257:
253:
242:
238:
234:
230:
226:
191:
187:
183:
179:
168:
164:
160:
151:
147:
143:
139:
105:
101:
97:
93:
71:Michael O. Rabin
21:
1038:
1037:
1033:
1032:
1031:
1029:
1028:
1027:
1023:Finite automata
1013:
1012:
1006:
988:
986:Further reading
983:
982:
955:
951:
929:
925:
893:
889:
874:
870:
862:
846:
842:
834:
830:
785:
778:
771:
755:
746:
739:
712:
708:
701:
679:Sipser, Michael
676:
667:
629:
625:
620:
612:Rabin automaton
603:
600:Büchi automaton
586:
574:
570:
566:
558:
554:
550:
542:
538:
534:
530:
526:
522:
511:
505:
486:
472:
463:
453:
449:
427:
421:
416:
398:
381:
370:
365:
362:
361:
354:
332:
326:
321:
306:
295:
290:
287:
286:
264:
255:
251:
240:
236:
232:
228:
193:
189:
185:
181:
177:
170:
166:
162:
159:
153:
149:
145:
141:
133:
118:
112:
103:
99:
95:
91:
83:
56:formal language
36:automata theory
28:
23:
22:
15:
12:
11:
5:
1036:
1026:
1025:
1011:
1010:
1004:
987:
984:
981:
980:
949:
923:
887:
868:
860:
840:
828:
806:cmp-lg/9804003
776:
769:
744:
737:
706:
699:
665:
646:(2): 114–125.
622:
621:
619:
616:
585:
582:
533:, there exist
507:Main article:
504:
501:
471:
468:
462:
459:
458:
457:
437:
433:
430:
424:
419:
415:
411:
408:
404:
401:
397:
394:
391:
384:
376:
373:
369:
358:
353:of each state
342:
338:
335:
329:
324:
320:
316:
309:
301:
298:
294:
283:
263:
260:
175:
157:
131:
111:
108:
82:
79:
26:
9:
6:
4:
3:
2:
1035:
1024:
1021:
1020:
1018:
1007:
1001:
997:
996:
990:
989:
975:
971:
967:
965:
959:
953:
945:
941:
937:
933:
927:
918:
914:
910:
906:
902:
898:
891:
883:
879:
872:
863:
861:9783540285205
857:
853:
852:
844:
837:
832:
824:
820:
816:
812:
807:
802:
798:
794:
790:
783:
781:
772:
766:
762:
761:
753:
751:
749:
740:
738:0-201-02988-X
734:
730:
726:
725:
720:
716:
710:
702:
700:0-534-94728-X
696:
692:
687:
686:
680:
674:
672:
670:
661:
657:
653:
649:
645:
641:
637:
633:
627:
623:
615:
613:
609:
601:
597:
593:
590:
581:
577:
562:
548:
515:
510:
500:
494:
490:
479:
475:
467:
431:
428:
422:
417:
409:
406:
402:
399:
395:
392:
374:
371:
359:
336:
333:
327:
322:
314:
299:
296:
284:
281:
276:
275:
274:
272:
271:
259:
249:
244:
224:
220:
216:
212:
208:
204:
200:
196:
174:
156:
137:
130:
126:
122:
117:
107:
88:
78:
76:
72:
68:
63:
61:
57:
53:
50:(NFA) into a
49:
45:
41:
37:
33:
19:
994:
961:
952:
935:
926:
900:
896:
890:
881:
877:
871:
850:
843:
831:
799:(1): 61–76.
796:
792:
759:
722:
709:
684:
643:
639:
632:Rabin, M. O.
626:
594:
587:
584:Applications
575:
560:
520:
498:
483:
473:
464:
282:application.
267:
265:
245:
222:
218:
214:
210:
206:
205:) = ∪{
202:
198:
194:
172:
154:
135:
128:
124:
120:
113:
110:Construction
84:
66:
64:
59:
43:
39:
29:
689:. pp.
192:to the set
140:, in which
966:(FOCS '88)
884:: 321–326.
618:References
547:worst-case
503:Complexity
235:. A state
75:Dana Scott
958:Safra, S.
917:206618275
660:0018-8646
636:Scott, D.
423:∗
418:ε
414:→
396:∈
390:∃
328:∗
323:ε
319:→
217:) |
81:Intuition
77:in 1959.
1017:Category
432:′
403:′
375:′
337:′
300:′
248:powerset
944:0175719
823:5622079
470:Example
270:closure
116:5-tuple
30:In the
1002:
942:
915:
858:
821:
767:
735:
697:
658:
387:
379:
312:
304:
87:prefix
38:, the
913:S2CID
819:S2CID
801:arXiv
729:22–23
691:55–56
602:with
123:, Σ,
1000:ISBN
901:C-20
856:ISBN
765:ISBN
733:ISBN
695:ISBN
656:ISSN
563:+ 1)
102:and
73:and
34:and
970:doi
905:doi
811:doi
648:doi
250:of
42:or
1019::
940:MR
911:.
899:.
880:.
817:.
809:.
797:26
795:.
791:.
779:^
747:^
731:.
717:;
693:.
668:^
654:.
642:.
634:;
580:.
578:=4
545:)
454:Q'
450:Q'
268:ε-
221:∈
134:,
127:,
1008:.
978:.
976:.
972::
946:.
921:.
919:.
907::
882:9
866:.
864:.
825:.
813::
803::
773:.
741:.
703:.
662:.
650::
644:3
604:n
576:n
571:n
567:2
561:n
559:(
555:n
551:n
543:2
539:2
535:n
531:n
527:2
523:n
487:T
456:.
436:}
429:q
410:q
407:,
400:Q
393:q
383:|
372:q
368:{
355:q
341:}
334:q
315:q
308:|
297:q
293:{
256:Q
252:Q
241:S
237:S
233:S
229:x
225:}
223:S
219:q
215:x
213:,
211:q
209:(
207:T
203:x
201:,
199:S
197:(
195:T
190:x
186:Q
182:S
178:}
176:0
173:q
171:{
167:Q
163:F
158:0
155:q
150:T
146:Σ
142:Q
138:)
136:F
132:0
129:q
125:T
121:Q
119:(
104:x
100:S
96:x
92:S
60:n
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
