オートマトンとは？

オートマトンの意味

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

オートマトンの具体例

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

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

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

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

• BNFとバッカス記法

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

• 次の状態遷移図で表現されるオートマトンで受理されるビット列はどれか。ここで，ビット列は左から順に読み込まれるものとする。

  正解：1010

  要点：受理列は0*1+0に続く任意列。1の後の0が鍵

  この状態遷移図は、初期状態で0を読み飛ばし、1が現れると次の状態へ移り、そこで1が続く限りとどまり、0を読んだ時点で受理状態に入って以降は何が来ても受理状態のままという構造になっている。つまり受理される列は「0が0個以上→1が1個以上→0→任意の列」という形である。この形にあてはまるのは1010で、1で第2状態へ移り、続く0で受理状態に達し、残りの10はそのまま受理状態を回る。

  出典：平成28年度 春期 基本情報技術者試験 午前 問2（IPA）

• 入力記号、出力記号の集合が{0, 1}であり、状態遷移図で示されるオートマトンがある。0011001110を入力記号とした場合の出力記号はどれか。ここで、S1は…

  正解：0001000110

  要点：オートマトンは入力を1文字ずつ追い、辺の出力側を順に並べる

  状態遷移図に従って入力を1文字ずつ処理し、遷移のラベルの出力側を並べればよい。初期状態S1から 0,0 は自己ループで出力0が2個。次の1でS1→S2（出力0）、続く1でS2→S3（出力1）。次の0でS3→S1（出力0）、0で自己ループ（出力0）、1でS1→S2（出力0）、1でS2→S3（出力1）、1はS3の自己ループ（出力1）、最後の0でS3→S1（出力0）。並べると 0001000110 となる。

  出典：平成30年度 春期 基本情報技術者試験 午前 問4（IPA）

• 入力記号、出力記号の集合が{0, 1}であり、状態遷移図で示されるオートマトンがある。0011001110を入力記号とした場合の出力記号はどれか。ここで、入力記…

  正解：0001000110

  要点：オートマトンは初期状態から遷移を順にたどり出力を並べる

  初期状態から入力を1文字ずつ読み、遷移のラベルに従って出力を並べる。出力が1になるのは、1が2つ以上続いて第3の状態へ入った後だけで、それ以外の遷移はすべて0を出力する。入力を順にたどると、2組目の1の位置と、その後に1が3つ続く箇所の2文字目以降で1が現れ、出力は0001000110となる。

  出典：令和4年度 s 基本情報技術者試験 kamokuA 問4（IPA）