技術士 第一次試験 基礎科目 2群 情報・論理 練習問題 第7問: 入力記号 0 と 1 を読む有限オートマトンがある。状態は A・B・C の 3 つで、初期状態は A、受理状態は C だけである。状態遷移は次のとおりとする。

「10010」が適切です。有限オートマトンは、状態の集合・初期状態・入力記号・遷移の規則からなり、初期状態から入力列を読んで状態を移していく計算のモデルで、受理状態を定めたものは入力列を受理するかを判定します（NIST Dictionary of Algorithms and Data Structures「finite state machine」）。

各入力列の状態の移り方は次のとおりです。

10010：A→A→B→C→B→C（最後が C で受理）

01001：A→B→A→B→C→B（最後が B）

1010：A→A→B→A→B（最後が B）

0011：A→B→C→B→A（最後が A）

11010：A→A→A→B→A→B（最後が B）

受理されるのは 10010 だけです。「01001」は途中で C を通りますが、最後の 1 で B に戻るので受理されません。

「1010」は初期状態を C と取り違えると C→B→C→B→C となり受理に見えます。「0011」は C で 1 を読んで C にとどまると読み違えると受理に見えます。