A DFA detecting substring 0011 needs states for matched prefixes ε,0,00,001, plus an absorbing “found” state, five total. These are distinguishable by completion suffixes. Complementing a complete DFA exchanges accepting states and preserves distinguishability, so the complement also needs five states, B.
More Regular Expressions and Finite Automata questions
GATE 2021 CS (CS2) Q19– Regular L⊆0,1* has a minimal DFA with k states. Which language necessarily also has a…
GATE 2021 CS (CS2) Q27– For the DFA shown, how many binary strings of length eight are accepted?
GATE 2021 CS (CS2) Q57– Which regular expressions denote the binary numbers divisible by three? Leading zeros are…
GATE 2026 CS (CS1) Q26– Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet.…
GATE 2026 CS (CS1) Q51– Let L 1 and L 2 be two languages over a finite alphabet, such that L 1 L 2 and L 2 are…
GATE 2026 CS (CS2) Q47– Consider the following two finite automata D 1 and D 2. Which of the following statements…