オートマトンとは？

オートマトンの意味

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

オートマトンの具体例

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

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

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

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

• BNFとバッカス記法

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

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

  正解：c

  要点：受理状態は目的の並びを読み終えた時点の状態

  初期状態aから110を読ませると、1でb、次の1でd、最後の0でcに至る。さらにcは0を読むとa、1を読むとbへ移り、末尾が110になった瞬間だけcに入る構造になっている。したがって受理状態はcとすればよい。

  出典：平成28年度 秋期 高度共通_午前I試験 am1 問2（IPA）