GATE 2017 CS – Question 32
Consider the language $L$ given by the regular expression $(a + b)^* b (a + b)$ over the alphabet $\{a, b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting $L$ is ________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 4
Explanation
The language is all strings whose second-to-last symbol is $b$. A DFA must remember the last two symbols read, which is 4 possibilities (aa, ab, ba, bb), and these are all distinguishable. So the minimum is 4 states.