情報セキュリティスペシャリスト平成21年春期 午前Ⅰ 問2

問2

次に示す有限オートマトンが受理する入力例はどれか。ここで,S1は初期状態を,S3は受理状態を表している。
  • 1011
  • 1100
  • 1101
  • 1110
  • [出典]
  • 応用情報技術者
    平成21年春期 問3と同題

分類

テクノロジ系 » 基礎理論 » 情報に関する理論

正解

解説

有限オートマトンは、入力値と入力されたときの状態で出力値が決まる順序機械に言語を識別するアルゴリズムを与えた数学的モデルです。

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

選択肢の中で唯一S3が受理可能な入力列は「1101」で出力順序は以下の通りです。
© 2014-2024 情報処理安全確保支援士ドットコム All Rights Reserved.

Pagetop