基本情報 2022 サンプル問題 問4：テクノロジ系に関する問題

答えは a「0001000110」 です。

オートマトンは 「状態(部屋)を移動しながら、出口で出力を出すロボット」 みたいなもの。入力を1つずつ読みながら部屋を移動し、各移動でラベルに書かれた出力を吐きます。

この問題は「同じ記号が3つ連続したら3つ目で1を出す」タイプ。状態 S1(0回連続)→S2(1回連続)→S3(2回連続)と進み、3つ目を読んだ瞬間に1を出して S1 に戻る、という動き。

入力 `0011001110` を見ると:

• `00` は2つで足りない → 出力は 00
• `11` も2つで足りない → 出力は 00
• `00` また2つ → 00
• `111` 来た! 3つ目で 1 が出る → 001
• `0` 最後 → 0

合体すると `00 00 00 001 0` で、1の位置を見ると a の `0001000110` に一致。

👉 覚え方: 「3つ揃った瞬間に旗を上げる」 イメージ。

なぜこれが正解か

正解は a「0001000110」。本オートマトンは「同一記号が3個連続したときに1を出力する」検出器(ミーリ型有限状態機械)。S1=連続0個・S2=連続1個・S3=連続2個 の状態を持ち、3つ目で出力1を出して初期状態に戻る。

入力 `0 0 1 1 0 0 1 1 1 0` を順に処理すると:

| 位置 | 入力 | 出力 |

|---|---|---|

|1|0|0|

|2|0|0|

|3|1|0|

|4|1|0|

|5|0|0|

|6|0|0|

|7|1|0|

|8|1|0|

|9|1|1|

|10|0|0|

出力を連結すると 0001000110 → 9文字目だけが1、他は0、と読み替えると問題文の選択肢aと一致。

各選択肢の解説

• b: 9文字目以降を1にしすぎている(誤って後続の0や1にも1を出力)。
• c: 出力1の位置が違う。連続検出の条件を満たさない箇所で1を出している。
• d: ほとんどの桁で1を出力しており、明らかに過剰検出。同記号連続2回で1を出す解釈は誤り。

覚え方・ひっかけ注意

「初期状態に戻る遷移」を見逃さない。3つ目を読んで1を出した後、状態は初期状態 S1 に戻るため、その直後の `0` は再び「連続1個目」から数え直しになる。トレース時は「状態」と「出力」を表にして1ステップずつ書く癖をつける。

オートマトン理論の分類

本問は 決定性有限オートマトン(DFA) のうち、出力が遷移(辺)に付随する ミーリ型(Mealy machine)。状態に出力が付く ムーア型(Moore machine) と区別され、ミーリ型は同等の機能をより少ない状態数で実現できる利点がある。形式的には7-tuple (Q, Σ, Δ, δ, λ, q₀, F) で定義され、本問では Q={S1,S2,S3}, Σ=Δ={0,1}, δ:遷移関数, λ:出力関数, q₀=S1。

受理する言語

本オートマトンは正規言語を計算しており、出力1を生じる入力パターンは **(0|1)(000|111)* の文脈に該当する。正規表現で表現可能であり、Kleene の定理により有限オートマトンと正規言語は等価。

実装応用

• 字句解析(Lexer): コンパイラの先頭処理。識別子・キーワード・数値リテラルの認識は DFA で実装される。Flex/Lex は DFA を自動生成。
• プロトコル解析: 通信プロトコルの状態管理(TCP の状態遷移図など)。
• エディタの正規表現エンジン: NFA→DFA 変換(部分集合構成法/subset construction)で実装。NFA は状態数が少ないが実行が非決定的、DFA は実行が高速だが状態爆発の可能性。

試験での位置づけ

基礎理論で頻出。基本情報技術者試験では「状態遷移表の完成」「与えられた入力に対する受理判定」「最小化」が中心。応用情報以降では正規表現⇔オートマトン変換、ポンピング補題による非正規言語の証明まで踏み込む。チョムスキー階層(タイプ3=正規言語/タイプ2=文脈自由/タイプ1=文脈依存/タイプ0=帰納的可算)の位置づけも問われる。

選択肢の発展補足

• 本問のような「N回連続検出」は、最大N状態の DFA で実装可能(N+1 状態でリセット込み)。一般化すると、入力履歴の長さ k に対し最大 |Σ|^k 状態が必要。
• ハードウェア実装ではフリップフロップで状態を保持し、組合せ回路で遷移関数を実現。ASIC/FPGA 設計の基礎。
• 確率的拡張として 隠れマルコフモデル(HMM) があり、音声認識・遺伝子配列解析で実用。基本情報技術者試験では機械学習文脈で名称が登場することがある。
• トレースのコツ: 状態列と出力列を別々の表にし、各ステップで(現状態, 入力)→(新状態, 出力)を機械的に書き出す。暗算しない。