Question 22

The language $L = (a + b)^* b (a + b)$ consists of all strings over $\{a, b\}$ whose second character from the right is $b$.

To determine the acceptance of any string, a DFA must track the last two symbols read:

• State $q_{00}$: last two symbols end in $aa$ (or at the start before any $b$ is read).
• State $q_{01}$: last two symbols end in $ab$ (second from right is $a$, most recent is $b$).
• State $q_{10}$: last two symbols end in $ba$ (second from right is $b$, most recent is $a$) - Accepting state.
• State $q_{11}$: last two symbols end in $bb$ (second from right is $b$, most recent is $b$) - Accepting state.

Let us verify state transitions:

• From $q_{00}$: on $a \to q_{00}$; on $b \to q_{01}$.
• From $q_{01}$: on $a \to q_{10}$; on $b \to q_{11}$.
• From $q_{10}$: on $a \to q_{00}$; on $b \to q_{01}$.
• From $q_{11}$: on $a \to q_{10}$; on $b \to q_{11}$.

All 4 states are pairwise distinguishable:

• $q_{00}$ and $q_{01}$ are rejecting, whereas $q_{10}$ and $q_{11}$ are accepting.
• $q_{00}$ on $a$ leads to $q_{00}$ (rejects with string $\epsilon$), whereas $q_{01}$ on $a$ leads to $q_{10}$ (accepts with string $a$). Hence, $q_{00} \not\equiv q_{01}$.
• $q_{10}$ on $b$ leads to $q_{01}$ (rejects with string $\epsilon$), whereas $q_{11}$ on $b$ leads to $q_{11}$ (accepts with string $b$). Hence, $q_{10} \not\equiv q_{11}$.

Therefore, the minimal DFA requires exactly 4 states.