情報に関する理論 (全41問中11問目)
No.11
次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。
出典：平成28年春期 問2
- 0000
- 0111
- 1010
- 1111
分類
テクノロジ系 » 基礎理論 » 情報に関する理論
正解
ウ
解説
設問のオートマトンでビット列が受理されるまでの流れは、
(2)と(4)の手順に注目すると、"1"の後には必ず1つ以上の"0"が含まれなければならないことがわかります。したがって選択肢のうち受理可能なビット列は「1010」のみです。
- "0"を0回以上繰り返す
- "1"を出力する
- "1"を0回以上繰り返す
- "0"を出力する
- "0"又は"1"を0回以上繰り返した後、受理される