平成25年度春期 応用情報技術者試験 午前 問3

正解：ウ

AI解説

偶数個の1を受理するオートマトンは、「これまでに読んだ1の個数が偶数か奇数か」の2状態をもつ。0を読んでも1の個数は変わらないので0は自分自身への遷移（自己ループ）、1を読むと偶奇が反転するので1は2状態間を行き来する遷移になる。初期状態は1が0個（偶数）なので受理状態と一致する。図の遷移ラベルに当てはめると a：1、b：0 のウが正しい。 ア: a：0、b：0とすると1を読んでも状態が変わらない遷移が生じ、1の個数の偶奇を数えられない。 イ: a：0、b：1では、0で偶奇が反転し1で変わらないことになり、1の個数ではなく0の個数を数える動きになってしまう。 ウ: 正しい。状態間を移る遷移aは偶奇を反転させる入力1、自己ループbは偶奇を変えない入力0である。 エ: a：1、b：1とすると、0を読んだときの遷移が定義と合わず、1を読んでも自己ループで偶奇が反転しない箇所が生じる。 💡 パリティ（偶奇）を数えるオートマトンは「対象の記号で状態が入れ替わり、それ以外は自己ループ」が定石。二重丸（受理状態）が初期状態でもあることから「1が0個＝偶数」を受理する点も確認する。