表は、入力記号の集合が{0, 1}、状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み込んで最後が110で終わっているものを受理するには、どの状態を受理状態とすればよいか。

選択肢

• アa
• イb
• ウc
• エd

正解と解説

正解：ウ c

受理状態は「末尾の3ビットが110である」ことを読み終えた直後の状態です。初期状態 a から1を読むと b、続けて1を読むと d へ進み、この d が「11を読み終えた」状態にあたります。さらに0を読むと c へ遷移するので、110を読み終えた時点の状態は c です。したがって c を受理状態にすればよいことになります。

選択肢ごとの解説

• アa は初期状態で、直前に0が続いている状況を表します。
• イb は1を1個読んだだけの状態で、110の読み終わりではありません。
• ウ正解。11を表す d から0を読んで到達する状態で、末尾110に対応します。
• エd は1が続いている状態で、末尾が1のまま終わることを意味します。

同じ分野の他の問題

• 誤り検出方式であるCRCに関する記述として、適切なものはどれか。2025年度 秋期 午前 問4
• 式A＋B×Cの逆ポーランド表記法による表現として、適切なものはどれか。2020年度 10月試験 午前 問3
• 符号長7ビット、情報ビット数4ビットのハミング符号による誤り訂正の方法を、次のとおりとする。 受信した7ビットの符号語x…2024年度 春期 午前 問4
• 図のように16ビットのデータを4×4の正方形状に並べ、行と列にパリティビットを付加することによって何ビットまでの誤りを訂…2021年度 秋期 午前 問4
• 逆ポーランド表記法（後置記法）で表現されている式ABCD-×+において、A=16、B=8、C=4、D=2のときの演算結果…2023年度 秋期 午前 問3