Dark Mode

omshiv
asked
in Theory of Computation
Dec 23, 2021

160 views
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