アルファベット {a, b} 上で、「a が3個以上連続する部分を含む」文字列だけを受理する DFA がある。この DFA が受理しない文字列はどれか。

解説

正解は「aabaab」です。この DFA は、直近に連続して読んだ a の個数（0, 1, 2）を状態として覚え、3個目の a を読んだら受理状態に入ってそのまま留まる、という4状態で作れます。aabaab では、a が2個続いた直後に必ず b が来て個数が0に戻るため、a が3個連続する部分がなく、受理されません。「baaab」は2〜4文字目に、「aaab」は1〜3文字目に、「abaaa」は3〜5文字目に aaa を含むので受理されます。このように「特定の文字列を部分として含む」言語は、その文字列のどこまで一致したかを状態として表すと、DFA を設計しやすくなります。