有限オートマトンとは？ゆうげんおーとまとん
有限オートマトンとは、有限個の状態と、入力記号による状態遷移で定義される計算モデル。入力を読み終えた時点で受理状態にあれば、その入力列を「受理する」と言う。字句解析や通信プロトコルの記述に使われる。
最終更新：2026-10-07
この語が出る過去問を解く →具体例
「0と1の列のうち、末尾が『101』であるもの」を受理する機械は、直近に読んだ並びを状態として覚えることで4状態程度で構成できる。
試験での引っ掛け
状態遷移表・遷移図から受理する文字列を答える問題では、途中で受理状態を通っても最後に受理状態にいなければ受理しない。
関連用語
出た過去問
出典：平成28年度 秋期 高度試験 午前Ⅰ 問2（IPA）
表は、入力記号の集合が{0，1}、状態集合が{a，b，c，d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から順に読み…
正解：c
要点：受理状態は目的の並びを読み終えた時点の状態
初期状態aから110を読ませると、1でb、次の1でd、最後の0でcに至る。さらにcは0を読むとa、1を読むとbへ移り、末尾が110になった瞬間だけcに入る構造になっている。したがって受理状態はcとすればよい。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (6) オートマトンに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。