アルファベット {a, b} 上で、「末尾から2番目の文字が a である」文字列だけを受理する DFA の最小の状態数はいくつか。

解説

正解は「4」です。末尾から2番目が a かどうかを判定するには、直近に読んだ2文字（aa, ab, ba, bb）を覚えておく必要があり、この4通りを状態とします。読み始めの状態は、先頭に b を補った bb と同じに扱えます。受理状態は直近2文字が aa か ab の状態です。この4状態は、続けて読む文字によって受理の結果が異なるので、どれもまとめられません。「2」は直前の1文字だけを覚える場合で、「末尾の文字が a」の言語の状態数です。「3」では直近2文字の4通りを区別できません。「8」は直近3文字を覚える場合で、「末尾から3番目が a」の言語の状態数です。NFA なら3状態で受理でき、DFA との差が表れる典型例です。