Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Use the algorithm below to convert the following Nondeterministic Finite Automaton into a Deterministic Finite Automaton
M = ({1,2,3},{a,b,c},{(1,a,3),(1,a,2),(2,a,3),(2,a,1),(2,b,2),(2,c,2)},1,{1,3})
Your solution should be a diagram of the machine produced by the algorithm.
Input: a nondeterministic finite automaton M = (Q,Σ,Δ,s,W), which has no λ-transitions
Output: a deterministic finite automaton M' such that L(M') = L(M).
M' = (2Q,Σ,δ, {s}, {R ∈ 2Q | R ∩ W ≠ ∅}) , where δ(H,x) = {q ∈Q | (p,x,q) ∈ Δ for some p ∈ H}

Problem 2

If the above algorithm is called on an NDFA $M$ with 8 states, how many states might the resulting DFA $M'$ have in the worst case?

Problem 3

Show how to modify the below machine to remove the $\lambda$-transition without changing the language the machine accepts.

Problem 4

Write an algorithm that matches the following specification (Hint: Think about Problem 3!):

Input: NDFA M = (Q,Σ,Δ,s,W) and triple (p,λ,q) ∈ Δ, where (p,λ,q) is the only λ-transition in the machine M.
Output: NDFA M' such that L(M') = L(M) and M' has no λ-transitions.

In case you're wondering what the point of this is, remember that the algorithm from Problem 1 is only valid if we have no λ-transitions. So getting rid of λ-transitions is an important job!