Question

1. Use the construction of Theorem 2.2 to convert the nfa in Figure 2.10 to a dfa. Can you see a simpler answer more directly?

Answer 1

======================================================================

Method to convert $\epsilon$ -nfa to dfa:

   consider $\epsilon$ -nfa: ( Q, $\Sigma$ , $\delta$ , q₀, F)

and equivalent dfa = (2^Q, $\Sigma$ , $\delta$ ', q, F') where q = $\epsilon$ -closure(q₀) , $\delta$ '(q,a) = $\epsilon$ -closure( $\delta$ (q,a))

=====================================================================

(1) In the given $\epsilon$ -nfa, $\Sigma$ = {a}

$\epsilon$ -closure(q₀) = { q₀}

So, initial state of DFA is {q₀}.

$\delta$ '({q₀},a) = $\epsilon$ -closure( $\delta$ (q₀,a)) = $\epsilon$ -closure(q₁) = {q_0, q₁,q₂}

$\delta$ '({q_0, q₁,q₂},a) = $\epsilon$ -closure{q_0, q₁,q₂} = {q_0, q₁,q₂}

So, equivalent DFA is:

	a
$\rightarrow$ {q0}	{q0, q1,q2}
{q0, q1,q2} F	{q0, q1,q2}

Regular expression corresponding to above DFA is a⁺.

(b) Given, $\delta$ (q0,a) = { q0, q1 }

               $\delta$ (q1,b) = { q1, q2}   // since $\delta$ (q1,a) is not given, then assume its $\phi$

               $\delta$ (q2,a) = {q2}

where initial state is q0 and final state is q2 in the given nfa.

Conversion from nfa to equivalent dfa:

$\delta$ ({q0},a) = { q0,q1}

$\delta$ ({q0},b) = $\phi$      //trap state

$\delta$ ({q0,q1},a) = {q0,q1}

$\delta$ ({q0,q1},b) = { q1,q2}

$\delta$ ({q1,q2},a) = {q2}

$\delta$ ({q1,q2},b) = {q1,q2}

$\delta$ ({q2},a) = {q2}

$\delta$ ({q2},b) = $\phi$

so, equivalent DFA is:

	a	b
$\rightarrow$ {q0}	{q0,q1}	$\phi$
{q0,q1}	{q0,q1}	{q1,q2}
{q1,q2} F	{q2}	{q1,q2}
{q2}F	{q2}	$\phi$

(c)  Given, $\delta$ (q0,a) = { q0, q1 }

               $\delta$ (q1,b) = { q1, q2}   // since $\delta$ (q1,a) is not given, then assume its $\phi$

               $\delta$ (q2,a) = {q2}

               $\delta$ (q1, $\epsilon$ ) = {q1,q2}

where initial state is q0 and final state is q2 in the given nfa.

Conversion from the given $\epsilon$ -nfa to its equivalent dfa:

$\epsilon$ -closure(q0) = {q0}

$\delta$ ({q0},a) = $\epsilon$ -closure({ q0,q1}) = {q0,q1,q2}

$\delta$ ({q0},b) = $\phi$      //trap state

$\delta$ ({q0,q1,q2},a) = $\epsilon$ -closure({q0,q1,q2}) = {q0,q1,q2}

$\delta$ ({q0,q1,q2},b) = $\epsilon$ -closure({ q1,q2}) = {q1,q2}

$\delta$ ({q1,q2},a) = $\epsilon$ -closure({q2}) = {q2}

$\delta$ ({q1,q2},b) = $\epsilon$ -closure({q1,q2}) = {q1,q2}

$\delta$ ({q2},a) = $\epsilon$ -closure({q2}) = {q2}

$\delta$ ({q2},b) = $\phi$

So, equivalent DFA is:

	a	b
$\rightarrow$ {q0}	{q0,q1,q2}	$\phi$
{q0,q1,q2}F	{q0,q1,q2}	{q1,q2}
{q1,q2}F	{q2}	{q1,q2}
{q2}F	{q2}	$\phi$