**Reading**-
Section 2.3 of
*Theory of Computing, A Gentle Introduction* **Homework**- Printout the homework and answer the questions on that paper.

**Algorithm: Non-Deterministic (w/o***λ*-transitions) to Deterministic FA-
Input: M = (Q,Σ,Δ,s,W), where Δ contains no *λ*-transitionsOutput: M' = (2 ^{Q},Σ,δ, {s}, {R ∈2^{Q}| R ∩ W ≠ ∅ }), whereδ : 2 ^{Q}x Σ → 2^{Q}δ(H,x) = { q ∈ Q | (p,x,q) ∈ Δ for some p ∈ H } **Example**- For further practice, run the above algorithm on the machine M = ({q0,q1},{a,b,c},{(q0,a,q0},(q0,c,q0),(q0,c,q1),(q1,a,q1),(q1,b,q1)},q0, {q1}).
**What about the***λ*-transitions?-
Our algorithm for converting non-deterministic finite automata into
deterministic finite automata doesn't work if we
have
*λ*-transitions. So, to round things out for us, we need an algorithm that takes a nondeterministic machine with*λ*-transitions and produces a new nondeterministic machine that accepts the same language, but which has no*λ*-transitions. The general idea is this: Suppose state*p*has an*λ*-transition to state*q*, and suppose that for character*x*you have transitions from state*q*to states*r1, r2, ..., rk*. Then essentially, if you're in state*p*and*x*is the next character in the input, you can either take any of*p*'s*x*-transitions or you can go to*q*and then take one of*q*'s*x*-transitions, which take you to*r1*, or*r2*or ... or*rk*. Thus, we can replace the*λ*-transition*(p,λ,q)*with the regular transitions*{(p,x,r) | x ∈ Σ and (q,x,r) ∈ Δ}*.}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. **Algorithm: Lose***λ*-transition-
**Input:***M = (Q,Σ,Δ,s,W)*and*(p,λ,q) ∈ Δ*, where there are no*λ*-transitions out of*q*.

**Output:***M' = (Q,Σ,Δ',s,W')*, where*Δ' = Δ - {(p,λ,q)} ∪ { (p,x,r) ∈ QxΣxQ | (q,x,r) ∈ Δ }*

*W' = W ∪ {p}*if*q ∈ W*, and*W*otherwise**Claim:***L(M') = L(M)*and there is one fewer*λ*-transition in*M'*than in*M*. **Algorithm: Lose***λ*-cycle-
**Input:***M = (Q,Σ,Δ,s,W)*and states*p1,p2,...,pk*comprising a cycle of 2 or more*λ*-transitions in*M*

**Output:***M' = (Q',Σ,Δ',s',W')**Q' = Q - {p1,...,pk} ∪ {D}*, where*D*is a new state i.e.*D ∉ Q*

*Δ' = Δ**- {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*s' = D*if*s ∈ {p1,...,pk}*, and*s*otherwise

*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*. **A full algorithm converting an NDFA into a DFA**-
Assume you're given a machine
*M = (Q,Σ,Δ,s,W)*which has no transitions of the form*(q,λ,q)*. This assumption is no real restriction, since such transitions are pointless and can simply be removed without affecting the language accepted by the machine. Set*M' = M*and then:- Apply Algorithm:
**Lose**repeatedly until there are no*λ*-cycle*λ*-cycles left in*M'*. This will only require a finite number of applications of the algorithm, since the number of λ-transitions decreases with every application of the algorithm. - Repeatedly apply Algorithm
**Lose**until there are no*λ*-transition*λ*-transitions left. This can only take a finite number of steps because the number of*λ*-transitions is finite, and each application of the algorithm reduces the number of*λ*-transitions. We are assured that we can always find a transition*(p,λ,q)*such that no*λ*-transitions come out of*q*because the machine has no*λ*-cycles. (Think about it!) Moreover, since we don't add new λ-transitions with this algorithm, no new cycles can appear. -
Apply the algorithm from Class
14 to convert the resulting nondeterministic machine
(which now has no
*λ*-transitions) into an equivalent deterministic finite automaton.

The deterministic finite automaton that results from this process accepts the same language as the original nondeterministic machine!

- Apply Algorithm:

Christopher W Brown Last modified: Mon Sep 28 15:55:53 EDT 2009