メインコンテンツへ
基礎理論

有限オートマトンに関する記述として、最も適切なものはどれか。

ア.状態数が無限に存在しうる計算モデルである。
イ.入力に応じて状態が遷移する、有限個の状態をもつ計算モデルである。正解
ウ.入力テープと書き換え可能な作業テープをもつ計算モデルである。
エ.スタックを補助記憶として用いる計算モデルである。

解説

有限オートマトンは「有限個の状態」と「状態遷移ルール」だけで動くシンプルな機械。信号機(赤→青→黄→赤…)が典型例です。

なぜ イ が正解か

イが正解。有限オートマトン(Finite Automaton)は文字どおり「状態の数が有限」で、入力記号を1つ読むたびに遷移関数に従って状態を移動する計算モデル。正規表現や字句解析器の理論的土台になっています。

なぜ ア は間違いか

状態が無限にあるなら、それは「有限」オートマトンではありません。語義そのものに反する選択肢で、用語のキーを読み飛ばすと拾ってしまいます。

なぜ ウ は間違いか

作業テープを書き換えながら計算するのはチューリングマシンの特徴。有限オートマトンには書き換え可能な記憶領域はありません。

なぜ エ は間違いか

スタックを補助記憶に使うのはプッシュダウンオートマトン(PDA)。文脈自由文法を認識できる別クラスのモデルで、有限オートマトンより表現力が一段上です。

出典: AI生成問題(学習用)