有限オートマトンとは？ゆうげんおーとまとん
有限オートマトンとは、有限個の状態と、入力によって状態が移る規則（状態遷移）で計算の振る舞いを表すモデル。状態遷移図や状態遷移表で表現し、入力列を最後まで読んだときに受理状態にいれば、その入力を受理したとみなす。正規表現（文字列の並び方の型を記号で書いたもの）の照合や、字句解析（プログラムの文字の並びを単語に切り分ける処理）、通信手順の設計の理論的な土台になる。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →具体例
「0の個数が偶数か」を判定するオートマトンは、「ここまでに読んだ0が偶数個」の状態と「奇数個」の状態の2つを持つ。0を読むたびに2つの状態を行き来し、1を読んでも状態は変わらない。入力を読み終えて偶数側にいれば受理。基本情報技術者試験では遷移表を与えて受理する入力列を選ばせる出題が多い。
試験での引っ掛け
状態数が有限なので、括弧の対応のような「数を無制限に覚える」処理は表現できない。また遷移表の読み方は「行＝現在の状態、列＝入力」が基本で、行と列を取り違えると答えがずれる。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 3. 情報に関する理論 ＞ (6) オートマトンに掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。