ACE Test Series

Question

Comments

4 ??

---

I am getting 3 .. (1,6),(2,5),(4,3) :/

Edit: (2,5) is an unreachable state so they have to be removed in the 1st step of minimization.

Answer should be (1,6)  and (4,3) according to me..

@Shamim Ahmed

Please check this now

---

I am not getting idea how to draw NFA for this transition table. Kindly help

---

@Shamim Ahmed

Just minimize the DFA from the transition table. The no. of states in the minimized DFA are the no. of equivalent classes.

---

3 equivalence classes .. [1] , [6] , [3,4]

---

Thanks i am also getting three states. {1,6}, {4,3}, {2,5}

---

How you are separating 1 and 6 ? They both fall under same equivalence class right?

Do we need to reject disconnected nodes in such questions or need to include them?

Answer 1

Myhill Nerode Theorem says that number of states in the smallest deterministic finite automata recognizing a language is equal to the number of equivalence classes in that language.

Minimizing the DFA we get the states : (1,6),(2,5),(3,4).

Number of states after minimization are 3 but (2,5) is unreachable state.

So.number of equivalence classes is 2.

Comments

here 2,5 are unreachable so we have to exclude them first hence the answer should be 2

---

@aanchal008

Why (1,6) can't be merged?

---

Thanks @aanchal008