有限オートマトンとは？
有限オートマトンとは、有限個の状態と、入力によって状態が移る規則（状態遷移）で計算の振る舞いを表すモデル。状態遷移図や状態遷移表で表現し、入力列を最後まで読んだときに受理状態にいれば、その入力を受理したとみなす。正規表現の照合や字句解析、通信手順の設計の理論的な土台になる。
ゆうげんおーとまとん
有限オートマトンの意味
有限個の状態と、入力によって状態が移る規則（状態遷移）で計算の振る舞いを表すモデル。状態遷移図や状態遷移表で表現し、入力列を最後まで読んだときに受理状態にいれば、その入力を受理したとみなす。正規表現の照合や字句解析、通信手順の設計の理論的な土台になる。
有限オートマトンの具体例
「0が偶数個」を判定するオートマトンは、偶数個の状態と奇数個の状態の2つを持ち、0を読むたびに行き来し、1を読んでも状態は変わらない。入力を読み終えて偶数側にいれば受理。FEでは遷移表を与えて受理する入力列を選ばせる出題が多い。
有限オートマトンは試験でどう引っ掛けられる？
状態数が有限なので、括弧の対応のような「数を無制限に覚える」処理は表現できない。また遷移表の読み方は「行＝現在の状態、列＝入力」が基本で、行と列を取り違えると答えがずれる。
有限オートマトンと関連する用語
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。