基本情報技術者 2016年春期午前（科目A）問02

問題文

次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで、ビット列は左から順に読み込まれるものとする。

🖊️ 解答を隠して解いてみる

選択肢

ア：0000

イ：0111

ウ：1010（正解）

エ：1111

🔒 解説は解答すると表示されます

有限オートマトンの受理言語【午前解説】

正解の理由

文字列 1010 を左から読むと次の遷移になります。開始状態（左端）で 1 を読むと中央へ移動（中央は非受理）、次に 0 を読むと右端の受理状態に到達します。受理状態に入った後は右端の自己ループ（0,1）でどんな文字が来ても受理状態に留まるため、残りの "10" を読んでも受理が維持されます。したがって 1010 は受理されます。

解法ステップ

オートマトンの状態を名前付け（左:start、中央:mid、右:accept）して考えます。
各文字を左から順に追い、現在の状態と対応する遷移を辿ります。
全文字を読み終えたときに最終状態が受理状態（右端の二重丸）かを確認します。
同様の問題では「受理条件を満たす最小パターン」（ここでは 1 のブロックの後の 0）を抽出すると判定が速くなります。
正規表現で表すと $0^{*} 1^{+} 0 (0∣1)^{*}$ となり、この形に合致するかをチェックするのも有効です。

選択肢別の誤答解説

ア: 0000
- 遷移: すべて 0 なので開始状態（左端）に留まる。開始状態は受理でないため不受理。
イ: 0111
- 遷移: 0 で左端に留まり、1 で中央へ移動、その後の 1 は中央の自己ループで中央に留まる。最終的に中央（非受理）で終了するため不受理。
ウ: 1010
- 遷移: 1（左→中央）、0（中央→右受理）、1（右受理に自己ループ）、0（右受理に自己ループ）で最終が受理状態。よって受理。
エ: 1111
- 遷移: 最初の 1 で中央へ移動し、その後の 1 は中央の自己ループで中央に留まる。入力終了時に中央（非受理）であるため不受理。

よくある誤解

中央の状態を「1 を読めば受理」と誤認する。中央は受理ではなく、さらに 0 を読んで右端へ遷移する必要があります。
「1 が含まれていれば受理される」と考える誤り。1 があってもその後に 0 が来なければ受理されません。
受理判定を部分的（途中で受理状態に一度到達したか）で判断する。必ず入力を全部読み終えたときの状態で判定します。

補足コラム

このオートマトンは最小化済みの DFA と見なせ、言語は「0 が任意個続いた後に 1 が少なくとも1つ続き、その直後に 0 が現れる文字列」すなわち正規表現で

0^{*} 1^{+} 0 (0∣1)^{*}

で表現できます。試験では全入力を読み終えた状態で判定する点を意識すると誤答が減ります。また受理状態に入ったら以降は残りを気にせず流せばよい（ループが全ての文字を許す場合）という視点も有用です。

FAQ

Q1: 「1 があれば中央に行き、そこで終了すれば受理では？」
A1: 中央は受理状態ではないため、そこで入力が終われば不受理です。必ず中央で 0 を読み右端へ行く必要があります。

Q2: 文字列 "10" は受理されますか？
A2: はい。1（左→中央）、0（中央→右）で右端受理状態に到達し、残りがなければ受理です。

Q3: 正規表現は何ですか？
A3:

0^{*} 1^{+} 0 (0∣1)^{*}

です。任意の 0 の後に 1 が1回以上続き、その直後に 0 が現れれば受理します。

関連キーワード: オートマトン、DFA、正規表現、受理状態、状態遷移図、部分語判定、文字列受理、有限オートマトン

← 前の問題へこの年度をクイズで解く次の問題へ →

\ せっかくなら /

基本情報技術者を
クイズ形式で学習しませんか？

クイズ画面へ遷移する→

すぐに利用可能！