Input: | M = | (Q,Σ,Δ,s,W), where Δ contains no λ-transitions | ||||||
Output: | M' = | (2Q,Σ,δ, {s}, {R ∈2Q | R ∩ W ≠ ∅ }), where | ||||||
|
Now, this idea works fine if there are not, in turn, λ-transitions out of q. The question is, if a machine has λ-transitions, can we always find at least one λ-transition to a state that has no λ-transitions? Then we could keep eliminating λ-transitions of that type until there weren't any at all. Unfortunately, there is one way that we could be unable to find an λ-transition to a state out of which there are no λ-transitions: What if there is a loop (or in graph parlance a cycle) of λ-transitions? So, first we need to get rid of any cycles of λ-transitions. Well, if there is a cycle of λ-transitions, the states in the cycle all form one big "super state", because whenever you're in one of the states you can get to any other without reading any input. So if there's a cycle, we'll merge all the states along the cycle into one state, wiping out all the λ-transitions between them in the process. This can simply be repeated until we finally arrive at a machine that has no cycles.
Δ' = Δ - {(p,λ,q)} ∪ { (p,x,r) ∈ QxΣxQ | (q,x,r) ∈ Δ }Claim: L(M') = L(M) and there is one fewer λ-transition in M' than in M.
W' = W ∪ {p} if q ∈ W, and W otherwise
Q' = Q - {p1,...,pk} ∪ {D}, where D is a new state i.e. D ∉ Q
s' = D if s ∈ {p1,...,pk}, and s otherwise
Δ' = Δ - {p1,...,pk}x(Σ ∪ {λ})xQ remove transitions out of the cycle - Qx(Σ ∪ {λ})x{p1,...,pk} remove transitions into the cycle ∪ {(D,x,q) ∈ {D}x(Σ ∪ {λ})xQ' | for some pi, (pi,x,q) ∈ Δ} add transitions out of D ∪ {(q,x,D) ∈ Q'x(Σ ∪ {λ})x{D} | for some pi, (q,x,pi) ∈ Δ} add transitions into D ∪ {(D,x,D) ∈ {D}xΣx{D} | for some pi and pj, (pi,x,pj) ∈ Δ} add D's loops
W' = W - {p1,...,pk} ∪ D if W ∩ {p1,...,pk} = ∅, and W otherwise
Claim: L(M') = L(M) and there are fewer λ-transitions in M' than in M.
The deterministic finite automaton that results from this process accepts the same language as the original nondeterministic machine!