情報に関する理論 (全42問中11問目)

No.11

次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで,ビット列は左から順に読み込まれるものとする。
02.gif/image-size:258×71
  • 0000
  • 0111
  • 1010
  • 1111

分類

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

正解

解説

設問のオートマトンでビット列が受理されるまでの流れは、
  • "0"を0回以上繰り返す
  • "1"を出力する
  • "1"を0回以上繰り返す
  • "0"を出力する
  • "0"又は"1"を0回以上繰り返した後、受理される
となります。(下図参照)
02a.gif/image-size:282×121
(2)と(4)の手順に注目すると、"1"の後には必ず1つ以上の"0"が含まれなければならないことがわかります。したがって選択肢のうち受理可能なビット列は「1010」のみです。
© 2010-2024 基本情報技術者試験ドットコム All Rights Reserved.

Pagetop