オートマトンとは？

オートマトンの意味

状態と、状態間を移る遷移規則（入力に応じてどの状態に移るか）の集合で表現される計算モデル。有限個の状態しか持たない「有限オートマトン」が代表的で、字句解析や正規表現の処理系に応用される。

オートマトンの具体例

自動販売機の「硬貨投入待ち→商品選択待ち→排出中」といった状態遷移は、状態遷移図（オートマトン）で表現できる。プログラムの状態遷移設計にも同じ考え方が使われる。

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

有限オートマトンが扱えるのは正規表現に対応する範囲まで。括弧の対応のように「いくつ開いたかを覚える」必要がある言語（文脈自由文法）は有限オートマトンでは認識できず、スタックを持つプッシュダウンオートマトンが要る。状態遷移図と状態遷移表は同じ内容の別の書き方で、どちらから読み取らせる出題もある。

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

• 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）