形式語言與計算模型
自動機理論研究抽象計算機器的數學模型，是形式語言、編譯器設計和計算複雜度的理論基礎。自動機從簡單的有限狀態機到複雜的圖靈機，構成了理解計算本質的層次結構。自動機理論的核心問題是：什麼樣的語言可以被機器識別？這個問題與「什麼可以被計算」密切相關。
┌─────────────────────────────────────────────────────────────┐ │ 自動機與語言的對應 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ 有限狀態機 ──▶ 正則語言 ──▶ 正則表達式 │ │ ↓ │ │ 下推自動機 ──▶ 上下文無關語言 ──▶ BNF │ │ ↓ │ │ 線性有界自動機 ──▶ 上下文敏感語言 │ │ ↓ │ │ 圖靈機 ──▶ 遞迴可枚舉語言 │ └─────────────────────────────────────────────────────────────┘
確定性有限自動機 (DFA) 的特點是每個狀態對每個輸入符號只有唯一確定的下一個狀態。形式定義：DFA = (Q, Σ, δ, q₀, F)。
範例：設計一個 DFA 識別包含子字串 "ab" 的所有字串：
轉移函數： - δ(q₀, 'a') = q₁, δ(q₀, 'b') = q₀ - δ(q₁, 'a') = q₁, δ(q₁, 'b') = q₂ - δ(q₂, 'a') = q₂, δ(q₂, 'b') = q₂
正則表達式是描述正則語言的另一種方式，與有限狀態機等價。語法包括：基本符號、空字串 ε、並聯 r|s、串聯 rs、克萊尼星 r*。正則表達式可以轉換為 NFA（使用 Thompson 構造），NFA 可以轉換為 DFA（使用子集構造），這個流程是編譯器詞法分析器的理論基礎。
"ab" — 匹配字串 "ab" "a|b" — 匹配 "a" 或 "b" "a*" — 匹配零或多個 "a" "(a|b)*" — 匹配任意數量的 a 和 b 的組合 "a*b*" — 匹配任意數量的 a 後跟任意數量的 b
下推自動機（PDA）比有限狀態機多了一個堆疊，這使其能夠識別上下文無關語言。下推自動機與上下文無關文法是等價的：一個語言是上下文無關的，當且僅當有一個下推自動機能夠識別它。
┌─────────────────────────────────────────────────────────────┐ │ 下推自動機結構 │ ├─────────────────────────────────────────────────────────────┤ │ │ │ ┌─────────┐ ┌─────────┐ ┌─────────────────────┐ │ │ │ 狀態控制 │─────▶│ 轉移函數 │─────▶│ 無限堆疊 │ │ │ └─────────┘ └─────────┘ │ ┌───┬───┬───┐ │ │ │ │ │ Z │ X │ Y │ ... │ │ │ │ │ └───┴───┴───┴──────│ │ │ └─────────────────────┘ │ └─────────────────────────────────────────────────────────────┘
範例語言：{aⁿbⁿ | n ≥ 1}（n 個 a 後跟 n 個 b）、匹配的括號等，這些需要「計數」或「配對」的能力。