Gate CSE Made Easy Test Series

Question

“Construct a minimal finite state automation that accepts the language over {0, 1} of all strings that contain neither the substring 00 nor the substring 11. What is the number of states in this machine?”

For this question when we draw the DFA there are 4 states and NFA contains 3 states minimum. So according to question what shall be the answer for this question? 3 or 4? Why?

Answer 1

The correct answer is 4 states for a minimal deterministic finite automaton (DFA) that accepts the language of all strings over {0, 1} containing neither the substring "00" nor the substring "11." The number of states in a DFA corresponds to the number of distinguishable states needed to recognize the language.

For this particular language, you need 4 states to distinguish between different substrings and ensure that the automaton recognizes the correct strings. Each state represents a different stage of reading the input and keeping track of whether the current substring contains "00" or "11."

If you draw a DFA with fewer than 4 states, it won't be able to distinguish between all possible strings in the language, and it will not be minimal. A minimal DFA is one that recognizes the language with the fewest possible states. In this case, a DFA with 4 states is the minimal DFA for the given language.

Comments

In the question, it is asked for minimal finite automata. Both NFA and DFA are finite state automata. So why have you not considered NFA for construction because it gives fewer states?

---

@abhiyodayapandey Many test series write a bit of incomplete questions assuming students would understand what to use, but the actual GATE examination always frames these types of questions properly, so don’t worry!