Convert the given NFA

Question

Question) Σ={a,b} and NFA is given in the following figure:

Using the procedure NFA to DFA, convert given NFA to DFA.
Using the reduce procedure, minimize the states in the DFA

I did a transition table for both nfa and dfa, but was stuck not knowing where q2 should go to, either q0 or make a new state calling it q4

Patrick87 Patrick87 · Accepted Answer · 2019-05-22T12:38:44

We can use the subset- or powerset-construction to go from the NFA to a DFA by considering subsets of the states of the NFA to be the potential states of a corresponding DFA. The initial state of our DFA will be {q0}, meaning that only q0 can be reached before reading any input. After reading an a from {q0}, we can reach q2 by consuming the a and then q0 again by taking the lambda-transition. Therefore, f({q0}, a) = {q0, q2}. Upon reading b in {q0}, we can only go to q1; so f({q0}, b) = {q1}.

We have introduced two new states, {q0, q2} and {q1}, in the DFA which we need transitions for. A moment's reflection will show that {q0, q2} has exactly the same transitions as {q0} does. On input a, q1 can go to q1, q2 or q0 (via q2); on input b, it can go to q2 or q0 (via q2). So, f({q1}, a) = {q0, q1, q2} and f({q1}, b) = {q0, q2}.

We have already seen {q0, q2} and know its transitions. However, we now need the transitions for {q0, q1, q2}. It seems that on input a, all of the states of the NFA can be reached from some state; the same is true of input b. So, f({q0, q1, q2}, a) = {q0, q1, q2} and f({q0, q1, q2}, b) = {q0, q1, q2}.

We did not introduce any new states on this iteration so we have all the states we could possibly need in a DFA. Our DFA looks like this:

q            s    q'
{q0}         a    {q0, q2}
{q0}         b    {q1}
{q0, q2}     a    {q0, q2}
{q0, q2}     b    {q1}
{q1}         a    {q0, q1, q2}
{q1}         b    {q0, q2}
{q0, q1, q2} a    {q0, q1, q2}
{q0, q1, q2} b    {q0, q1, q2}

All of the states except {q1} are accepting since they all contain the accepting state q0 from the NFA. Now, before we minimize this DFA, let's rename the states:

qA = {q0}
qB = {q0, q2}
qC = {q1}
qD = {q0, q1, q2}

We can iteratively cross off pairs of states that cannot be combined as follows:

   qA,qB    qA,qC    qA,qD    qB,qC    qB,qD    qC,qD
   --------------------------------------------------
1.          xxxxx             xxxxx             xxxxx
Reason: qC cannot be combined with others since it is
        not accepting and the others are

2.                   xxxxx             xxxxxx
Reason: f((qA, qD), b) and f((qB, qD), b) equal (qC, qD)
        which was crossed off during the last iteration.

qA,qB cannot be crossed off, so these states can be
combined in a minimal DFA.

The resulting minimal DFA is:

q            s    q'
qAB          a    qAB
qAB          b    qC
qC           a    qD
qC           b    qAB
qD           a    qD
qD           b    qD

Convert the given NFA

1 Answers