有限オートマトンとは？ゆうげんおーとまとん
有限オートマトンとは、有限個の状態と、入力記号による状態遷移の規則で定義される計算モデル。入力列を先頭から1記号ずつ読み進め、読み終えた時点の状態が受理状態であればその入力列を受理する。覚えていられるのは現在の状態だけで、回数を無制限に数えるような記憶は持てない。
最終更新：2026-10-06
この語が出る過去問を解く →背景
文字列が仕様どおりの形をしているかを機械に判定させたいが、判定器に無限の記憶を持たせることはできない。状態の数を有限に固定したうえで何が判定できるかを見極めたのが有限オートマトンで、この制約の範囲に収まる言語が正規言語にあたる。シラバスでは形式言語やチューリング機械との関係として位置づけられ、状態遷移表・状態遷移図の読み取りが具体的な出題形態になる。
具体例
grepやlexといったツールは、与えられた正規表現をいったん状態遷移の表に変換し、入力を1文字ずつ走査しながら状態を移して照合する。通信プロトコルのハンドシェイク手順も、確立待ち・確立済み・切断中といった状態と遷移条件の組として仕様が書かれる。
試験での引っ掛け
状態遷移図から受理する文字列を選ばせる問題では、途中で受理状態を通過しても入力を読み終えた時点で受理状態にいなければ受理しない。もう一つは能力の限界で、括弧の対応やaがn個の次にbがn個といった数の対応は状態を有限にしたままでは扱えず、プッシュダウンオートマトン以上が要る。
関連用語
出た過去問
出典：平成28年度 秋期 応用情報技術者試験 午前 問4（IPA）
表は、入力記号の集合が{0, 1}、状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から…
正解：c
要点：受理状態はパターンを読み終えた直後に到達する状態
受理状態は「末尾の3ビットが110である」ことを読み終えた直後の状態です。初期状態 a から1を読むと b、続けて1を読むと d へ進み、この d が「11を読み終えた」状態にあたります。さらに0を読むと c へ遷移するので、110を読み終えた時点の状態は c です。したがって c を受理状態にすればよいことになります。
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (6) オートマトンに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。