Name: ____________________________________________________ Alpha: _____________________
Describe help received: _________________________________________________________________
Problem 1
Use the algorithm below (i.e. the one we walked through in class)
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.
Algorithm: NDFA-to-DFA Conversion
Input: a nondeterministic finite automaton
$M = \left(Q,\Sigma,\Delta,s,W\right)$, which has no
$\lambda$-transitions
Output: a deterministic finite automaton $M'$
such that $L(M') = L(M)$.
$
M' = \left( 2^{Q}, \Sigma, \delta, \{s\}, \{ R \in 2^{Q}\ |\ R
\cap Q \neq \emptyset \} \right)
$, where
$\delta(H,x) = \{ q \in Q \ |\ (p,x,q) \in \Delta \text{ for
some } p \in 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!