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 _________.

The given regular expression is $L = (a+b)^*b(a+b)$, which describes the set of all strings over $\{a, b\}$ whosesecond symbol from the right is $b$.

In general, for an alphabet of size 2, a DFA that checks whether the $k$-th symbol from the right is a specific symbol requires $2^k$ states, because it must remember the last $k$ symbols seen.

Here $k = 2$, so the minimum number of states is:

The 4 states corresponding to the suffix of the last 2 symbols processed are:

• $q_0$: Initial state (suffix $\epsilon$ or ends with $aa$)

• $q_1$: Suffix ends with $a$ (specifically preceded by something not enabling acceptance, i.e., seen $ba$ or $a$)

• $q_2$: Suffix ends with $b$ (second symbol from right is not yet $b$)

• $q_3$: Suffix is $ba$ or $bb$ (accepting states where the second symbol from right is $b$)

Explicitly, the state set $\{q_{aa}, q_{ab}, q_{ba}, q_{bb}\}$ or the standard Myhill-Nerode equivalence classes give exactly 4 states.