The subset construction is a technique of turning a non-deterministic automaton into a deterministic one, while keeping the accepting language the same. This technique shows that an NDFA is no more powerful in terms of word acceptance than a DFA.
for any subset of and . Note that . What we have just done is turning a semiautomaton into a deterministic semiautomaton , where , the powerset of .
It is easy to see, by induction on the length of , that .
Next, given an NDFA , we turn it into a DFA as follows:
is derived from by the construction above,
Since is an element of , and , is a well-defined DFA.
iff (where ) iff iff . ∎
What happens if the NDFA in question contains -transitions (http://planetmath.org/EpsilonTransition)? Suppose is an -transition, and . Then , which is not allowed in a DFA.
To get around this difficulty, we make a small modification on . First, define, for any , the -closure of as the set
For any , . If the automaton does not contain any -transitions, then .
Now, let NDFA be an -automaton (http://planetmath.org/EpsilonAutomaton), define as follows:
, where is defined in (1) above,
|Date of creation||2013-03-22 19:02:00|
|Last modified on||2013-03-22 19:02:00|
|Last modified by||CWoo (3771)|