オートマトンと形式言語

計算モデルを表現力の階層で整理する計算理論の基礎。受理する文字列の集合をそのオートマトンの言語と呼ぶ。

有限オートマトン (FA)

状態遷移図で表される最も単純なモデル。DFA $A=(Q,\Sigma ,q_0,A,\delta )$（状態・入力アルファベット・開始状態・受理状態・遷移関数）。遷移先が一意なら DFA、そうでなければ NFAだが、NFA は必ず DFA に変換でき表現力は同じ。受理できる言語が正規表現。限界として $L=\{a^k{b}^k\}$ は受理できない。

プッシュダウンオートマトン (PDA)

有限オートマトンにスタックを付けて履歴を記憶できるようにしたもの。$\{a^k{b}^k\}$ を受理でき、FA より表現力が高い。PDA で受理できる言語が**文脈自由文法 (CFG)**（生成規則で定義、いわゆる構文解析の対象）。限界として $\{a^k{b}^k{c}^k\}$ は受理できない。

チューリングマシンと決定不能性

• 万能チューリングマシン: 別の TM の記述をテープ入力として受け取り、その動作をエミュレートする TM。
• 停止性問題: 任意の TM が停止するか判定する TM は作れない（決定不能）。ゲーデルの不完全性定理（証明も反証もできない命題の存在）や連続体仮説とも関連する。

関連

• 構文解析は言語処理系、計算モデルとしてはλ計算と等価。
• _moc-prog-lang