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