in Theory of Computation
160 views
0 votes
0 votes

in Theory of Computation
by
160 views

1 Answer

0 votes
0 votes
Best answer

Answer : 4

Reason : $Q_0$ and $Q_2$ are equivalent states.

Solution : Here is a method to solve it faster

Step 1 : for ease write state by numbers and next state for 0,1 in as a tuple.

  • $0 (1,2)$
  • $1 (1,4)$
  • $2 (1,2)$
  • $3 (1,2)$
  • $4 (1,3)$

Tip : since all go to same state for input $0$ we will check only for input $1$. 

Step 2 : Begin procedure of equivalence theorem,

$\rightarrow0$ Equivalance : First group $G_1$ of non final states and final group $G_f$ of final states.

  • $(0,2,4)(1,3)$

$\rightarrow1$ Equivalance : In $G_1$ $(0,2)$ stay in $G_1$ only $4$ goes to $G_f$ so $4$ is new group $G_2$

  • $(0,2)(4)(1,3)$

$\rightarrow2$ Equivalance : In $G_f$ $1$ goes to $G_2$ and $3$ goes to $G_1$ so $1$ is new group $G_3$

  • $(0,2)(4)(1)(3)$

$\rightarrow3$ Equivalance : In $G_1$ both $(0,2)$ goes to $G_1$ so no change and we have final 4 states.

  • $(0,2)(4)(1)(3)$

 

PS : Theoretical  method of answering,

The given DFA accepts string that end with 0 or 011,so we need

one state for ending in 0, final state

one state for handling 01 ,intermediate state,

one state for 011 ,final state

and one state where we have 1 at the end without having 3rd last symbol 0 i.e not 011

selected by