上下文无关语言学习卡片

📝

上下文无关文法 (CFG)

点击查看详情

定义: 四元组 G = (V, Σ, S, R)，其中：; - V: 符号集合; - Σ: 终结符集合; - S: 开始符号; - R: 产生式规则集合
推导: - 一步推导: ⇒_G; - 多步推导: ⇒_G*
语言生成: L(G) = {w ∈ Σ* | S ⇒_G* w}

📐

乔姆斯基范式 (CNF)

点击查看详情

规则形式: 1. S → ε; 2. A → BC (B, C ∈ V-Σ-{S}); 3. A → a (a ∈ Σ)
定理: 每个CFG都有等价的CNF形式
推导次数: 生成长度 n>0 的字符串需要：; - 2n-1 次推导; - n-1 次使用规则(b)扩展长度; - n 次使用规则(c)替换为终结符

🤖

下推自动机 (PDA)

点击查看详情

定义: P = (K, Σ, T, Δ, s, F); - K: 状态集合; - Σ: 输入字母表; - T: 栈字母表; - Δ: 转移关系; - s: 初始状态; - F: 终止状态集合
配置: (p, w, α) ∈ (K × Σ* × T*); 表示当前状态、未读输入和栈内容
接受条件: 到达终态且栈为空

🔄

CFG ⇔ PDA

点击查看详情

CFG → PDA: 在栈上不确定地使用G生成字符串，与输入比较，匹配则接受
简单PDA: 只有一个终态，每个转移要么只pop一个，要么只push一个
PDA → CFG: PDA → 简单PDA → CFG

💧

CFL泵引理

点击查看详情

定理: 若L是CFL，则存在泵长度p∈Z*，使得∀w∈L且|w|≥p，可划分为w=uvxyz，满足：
条件: 1. ∀i≥0, uvⁱxyⁱz ∈ L; 2. |v| + |y| > 0; 3. |vxy| ≤ p
应用: 证明语言不是上下文无关的; 例如: L = {aⁿbⁿcⁿ : n≥0} 不是CFL

🔒

CFL封闭性

点击查看详情

封闭运算: ✅ 并集 (Union); ✅ 连接 (Concatenation); ✅ 克林闭包 (Kleene Star)
不封闭运算: ❌ 交集 (Intersection); ❌ 补集 (Complement)
特殊性质: CFL与RL的交集仍是CFL

记忆提示: CFL对并、连接和星号封闭，但对交和补不封闭。