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

解説

正解は「4」です。受理の判定には、それまでに読んだ a の個数の偶奇と b の個数の偶奇を覚えておく必要があり、その組合せは（偶, 偶）（偶, 奇）（奇, 偶）（奇, 奇）の4通りです。a を読むと a の偶奇が、b を読むと b の偶奇が反転し、（偶, 奇）だけを受理状態とします。この4状態はどの2つも、適当な入力列を続けると受理か否かが分かれるので、まとめられません。「2」は a か b の一方の偶奇だけを覚える場合の状態数です。「3」では4通りの組合せを区別できません。「5」は、受理できない文字列を吸収する死に状態を余分に加えた数です。この言語ではどの状態からでも受理状態に戻れるため、死に状態は不要です。