Question

Consider the language L given by the regular expression $(a+b{)}^{\ast }b(a+b)$ over the alphabet $\{a,b\}$. The smallest number of states needed in a deterministic finite-state automaton (DFA) accepting L is

Answer 1

The r.e is $(a+b{)}^{\ast }b(a+b)$

This is all strings whose second last bit is 'b' Minimal NFA is

Converting it into minimal DFA by subset construction algorithm, we get

Which is a minimal DFA with 4 states.