計算理論の基礎であるオートマトン (有限状態機械)。コンパイラやプロトコル設計の土台となる概念を学びます。
日野 こむぎ
オートマトンって、なんか難しそう…
藤森 さやか 先生
イメージは簡単よ。
オートマトンは「状態と遷移」で動作を表現する数学モデルなの。
自販機のような身近なものもオートマトンで表現できるわ。
青木 澪
代表は有限オートマトン (FA・Finite Automaton)。
状態が有限個で、入力1文字ごとに次の状態に遷移する仕組み。
決定性有限オートマトン (DFA) と非決定性有限オートマトン (NFA) の2種類があるの。
桃井 すみれ
どんなところで使われてるんですかぁ?
青木 澪
プログラミング言語の字句解析 (lexer)・正規表現・通信プロトコルの状態遷移・ゲームAIなど、幅広く使われているわ。
藤森 さやか 先生
オートマトンの上位概念にプッシュダウンオートマトン (PDA、スタック付き) やチューリングマシン (テープ付き、計算可能性の極限) があり、計算理論の階層を形成しているの。
青木 澪
試験では「状態遷移図を読み取る」「次の入力に対する遷移後の状態を答える」といった問題が出ますよ。
日野 こむぎ
じゃあ信号機もオートマトンってこと?
青→黄→赤→青…って状態遷移してるじゃん!
確認クイズ
プログラミング言語のソースコードを「識別子・数値・記号」などのトークンに分解する処理を何と呼ぶか。
- 字句解析 (lexer)
- 構文解析 (parser)
- 意味解析
- コード生成
こたえを見る
正解: 1. 字句解析 (lexer)
字句解析 (Lexical Analysis / Lexer) はソースコードをトークンに分解する処理で、有限オートマトン (FA) で実装されることが多いコンパイラの第1段階です。