Question 50

Label the states from left to right as $q_0$ (start), $q_1$, $q_2$, and $q_3$ (accept):

• $q_0$: Longest suffix matching a prefix of bab is $\epsilon$ (on $a \to q_0$, on $b \to q_1$).
• $q_1$: Longest matching suffix is b (on $b \to q_1$, on $a \to q_2$).
• $q_2$: Longest matching suffix is ba (on $a \to q_0$ since baa has no non-empty prefix of bab as suffix; on $b \to q_3$).
• $q_3$ (accepting): Longest matching suffix is bab (on $a \to q_2$ since baba ends with ba; on $b \to q_1$ since babb ends with b).

Because the DFA leaves the accepting state $q_3$ whenever the string no longer ends with bab, it accepts precisely the set of all strings ending with the pattern $bab$.