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' =
(2*^{Q},Σ,δ, {s}, {R ∈
2^{Q} | 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!