有限オートマトンとは？

有限オートマトンとは、有限個の状態と、入力記号による状態遷移で定義される計算モデル。入力を読み終えた時点で受理状態にあれば、その入力列を「受理する」と言う。字句解析や通信プロトコルの記述に使われる。

高度試験・午前I（全区分共通）の過去問では1回出題されています。

ゆうげんおーとまとん

高度試験・午前I（全区分共通）の頻出用語／午前I（全区分共通）／別名：状態遷移機械、FA

有限オートマトンの意味

有限個の状態と、入力記号による状態遷移で定義される計算モデル。入力を読み終えた時点で受理状態にあれば、その入力列を「受理する」と言う。字句解析や通信プロトコルの記述に使われる。

「0と1の列のうち、末尾が『101』であるもの」を受理する機械は、直近に読んだ並びを状態として覚えることで4状態程度で構成できる。

状態遷移表・遷移図から受理する文字列を答える問題では、途中で受理状態を通っても最後に受理状態にいなければ受理しない。

表は、入力記号の集合が{0，1}、状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み…
正解：c
要点：受理状態は目的の並びを読み終えた時点の状態
初期状態aから110を読ませると、1でb、次の1でd、最後の0でcに至る。さらにcは0を読むとa、1を読むとbへ移り、末尾が110になった瞬間だけcに入る構造になっている。したがって受理状態はcとすればよい。
出典：平成28年度秋期高度共通_午前I試験 am1 問2（IPA）

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。