ACE Test Series

Question

Comments

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