Test by Bikram | Theory of Computation | Test 2 | Question: 9

Question

Consider the following transition table of DFA where $q3$ is the final state:

$\begin{array}{|c|c|c|} \hline {} & x & y \\ \hline \rightarrow q0 & q1 & q0 \\ \hline q1 & q0 & q2 \\ \hline q2 & q3 & q1 \\ \hline  +q3 & q3 & q0 \\ \hline q4 & q3 & q5 \\ \hline q5 & q6 & q4 \\ \hline q6 & q5 & q6 \\ \hline q7 & q6 & q3 \\ \hline \end{array}$

The number of states required to represent the same language with minimum number of states automata is _________.

Comments

@Bikram sir,

here i think answer should be 5,

{q0, q1, q2, q4, q5, q6, q7}   {q3} // 0 equivalent

{q0, q1, q5, q6}   {q2, q4}   {q7}   {q3} // 1 equivalent

{q0, q6}   {q1, q5}   {q2, q4}   {q7}   {q3} // 2 equivalent

{q0, q6}   {q1, q5}   {q2, q4}   {q7}   {q3} // 3 equivalent

since 2 equivalent and 3 equivalent are equal we stop and say that there are 5 states in minimized dfa.

---

@joshi

plz check the answer .

---

@Bikram sir

thanks, answer will be 4, i didnt noticed that q4, q5, q6, q7 are not reachable from q0..

Answer 1

The DFA for the given transition table.

In the red portion of the image, there is no incoming edge. Means the states q4, q5, q6 q7 are not reachable. So we can directly remove them.

We don't need to draw dfa to see that it can also be seen directly from the translation table.

Now, {q0, q1, q2}, {q3}.    // 0 equivalence.

{q0, q1}, {q2}, {q3}    // 1 equivalence.

{q0}, {q1}, {q2}, {q3}   // 2 equivalence.

Minimal DFA will have 4 states.