有限オートマトンとは？

有限オートマトンの意味

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

有限オートマトンの具体例

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

有限オートマトンは試験でどう引っ掛けられる？

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

有限オートマトンと関連する用語

• BNF（バッカス・ナウア記法）
• 正規表現

有限オートマトンが出た過去問

• 表は、入力記号の集合が{0, 1}、状態集合が{a, b, c, d}である有限オートマトンの状態遷移表である。長さ3以上の任意のビット列を左（上位ビット）から…

  正解：c

  要点：受理状態はパターンを読み終えた直後に到達する状態

  受理状態は「末尾の3ビットが110である」ことを読み終えた直後の状態です。初期状態 a から1を読むと b、続けて1を読むと d へ進み、この d が「11を読み終えた」状態にあたります。さらに0を読むと c へ遷移するので、110を読み終えた時点の状態は c です。したがって c を受理状態にすればよいことになります。

  出典：平成28年度 秋期 応用情報技術者試験 午前 問4（IPA）