情報に関する理論(全50問中34問目)

次に示す有限オートマトンが受理する入力例はどれか。ここで,S1は初期状態を,S3は受理状態を表している。
03.gif

出典:平成21年春期 問 3

  • 1011
  • 1100
  • 1101
  • 1110
正解 問題へ
分野:テクノロジ系
中分類:基礎理論
小分類:情報に関する理論
解説
有限オートマトンは、入力値と入力されたときの状態で出力値が決まる順序機械に言語を識別するアルゴリズムを与えた数学的モデルです。

この有限オートマトンを文章で表すと、
  1. S1状態から始まる。
  2. S1状態で0を出力した時はS3へ、1を出力した時はS2へ状態遷移する。
  3. S2状態で0を出力した時はS2を維持、1を出力した時はS1へ状態遷移する。
  4. S3状態で0を出力した時はS2へ状態遷移し、1を出力した時はS3を維持する。
  5. 入力列はS3で受理される。
ということになります。

選択肢の中で唯一S3が受理可能な入力列は「1101」で出力順序は以下の通りです。
03a.gif

Pagetop