Context-Free Language && Push-Down Automata

Context-Free Language && Push-Down Automata

上下文无关语言

课件中有习题

Context-Free Language

Context Free Grammar(CFG) 上下文无关文法

上下文无关文法是一个元组$G=（N,T,S,P）$

• N:一个有限的其他符号的集合，每个符号代表了一个语言，称为 非终结符(Non-terminals)

• T:终结符（terminals）的有限集合

• $S\in\epsilon$:起始非终止符 start non-terminals

• P:产生式 productions

  • 形式是 $A\to a$
  • $A\in \epsilon$

  • $a\in (N \cup T)^*$

  • 比如 assignment->identifier = expression

Derivation 推导 $\Rightarrow _G$

表示经过零步或若干步推导，记作 $\Rightarrow ^*$

Left-Most Derivation 最左推导 $\Rightarrow_{lm}$

最左推导优先替换左边的非终止符 最右推导优先替换右边的非终止符

歧义 一个字符串有两种推导树

固有歧义 inherent ambiguity

• 有些上下文无关语言仅存在歧义文法
• 我们无法消除这种歧义
• 目前没有通用技术可以消除歧义
• 不存在能够判定一个文法是否歧义的算法（这是一个不可判定的问题）

减少歧义的方法

• 提高特定运算符的优先级
• 提升已匹配的语句的优先级。

Push-Down Automata

下推自动机（Pushdown Automaton, PDA）是一种扩展的有限自动机，通过引入栈（Stack） 来处理更复杂的语言（如上下文无关语言）

---

1. PDA 的组成部分

一个 PDA 可以形式化定义为七元组：M=(Q,Σ,Γ,δ,q0,Z0,F)

• Q：有限状态集合。
• Σ：输入符号表（终结符）。
• Γ：栈符号表（可包含终结符和非终结符）。
• δ：转移函数，定义状态转移规则。
• q~0~：初始状态（q0∈Qq0∈Q）。
• Z~0~：初始栈顶符号（Z~0~∈Γ）。
• F：接受状态集合（F⊆Q）。

---

2. 转移函数的结构

转移函数的形式为：

δ:Q×(Σ∪{ϵ})×Γ→有限集合 Q×Γ^∗^

• 输入：当前状态、输入符号（或空字符 ϵϵ）、栈顶符号。
• 输出：新状态和要推入栈的符号序列（例如，弹出栈顶符号后推入新符号）。

示例：

δ(q,a,X)={(p,YZ)}

表示在状态 q，读取输入符号 a，栈顶为 X时，转移到状态 p，弹出 X，并推入 YZ。

---

3. PDA 的两种接受方式

1. 通过最终状态接受：输入字符串处理完毕后，PDA 处于某个接受状态 q~f~∈F。
2. 通过空栈接受：输入处理完毕后，栈为空（无论最终状态是否在接受状态集合中）。

注：这两种接受方式在表达能力上是等价的，即任何通过最终状态接受的 PDA 可转换为通过空栈接受的 PDA，反之亦然。

---

4. PDA 的工作原理

以下以识别平衡括号语言 {(n)n∣n≥0}为例：

• 栈的初始符号：Z~0~。
• 规则设计：
  1. 遇到左括号 (：推入栈中（例如，推入 X）。
  2. 遇到右括号 )：弹出栈顶符号 X。
  3. 输入结束时，栈应为空。

转移函数示例：

δ(q~0~,(,Z~0~)=(q~0~,XZ~0~)（推入 X）

δ(q~0~,(,X)=(q~0~,XX)（继续推入 X）

δ(q0,),X)=(q0,ϵ)（弹出 X）

δ(q~0~,ϵ,Z~0~)=(q~f~,Z~0~)（接受空字符串）

说明：

• 每次读取 ( 推入 X，读取 ) 弹出 X。
• 若输入结束时栈中只剩 Z~0~，则接受字符串。

---

5. PDA 与上下文无关文法（CFG）的关系

• CFG 到 PDA 的转换： 每个产生式 A→α 对应 PDA 的转移规则，将非终结符 A*弹出栈，并推入 α 的反转序列。 示例：对于文法 S→(S)∣ϵ，对应的 PDA 规则为：

  δ(q,ϵ,S)={(q,(S)),(q,ϵ)}

• PDA 到 CFG 的转换： 通过模拟 PDA 的栈操作，生成等价的上下文无关文法，具体方法较复杂（需引入变量表示状态和栈内容）。

---

6. PDA 的局限性

• 无法处理所有语言：例如，无法识别 {a^n^b^n^c^n^∣n≥0}（需图灵机）。
• 能力介于有限自动机与图灵机之间：PDA 识别上下文无关语言，而图灵机可识别递归可枚举语言。

非确定型下推自动机（Nondeterministic Pushdown Automaton, NPDA） 是一种扩展的下推自动机（PDA），允许在同一输入符号和栈顶符号下存在多个可能的转移路径。这种非确定性使得 NPDA 能够识别所有上下文无关语言（CFL），而确定型下推自动机（DPDA）仅能识别确定性上下文无关语言（DCFL），后者是 CFL 的真子集。

与 DPDA 的核心区别：

• DPDA：对于每个状态、输入符号和栈顶符号，转移函数至多有一个可能的动作。
• NPDA：允许转移函数返回多个可能的动作（状态和栈操作组合），通过“猜测”选择正确路径。

---

2. NPDA 的形式化定义

一个 NPDA 可定义为七元组：M=(Q,Σ,Γ,δ,q0,Z0,F)

转移函数示例：

δ(q,a,X)={(p,YZ),(r,ϵ)}

表示在状态 q，输入符号 a，栈顶符号 X时，可以选择：

1. 转移到状态 p，弹出 X，推入 YZ。
2. 转移到状态 r，弹出 X，推入空（即仅弹出 X）。

特性	NPDA	DPDA
非确定性	允许同一输入和栈顶下多路径转移	每个输入和栈顶至多一个转移路径
接受语言类	所有上下文无关语言（CFL）	确定性上下文无关语言（DCFL）
典型应用	处理歧义性、嵌套结构	解析编程语言（需确定性）
示例语言	{anbn}{anb**n}, 回文	{anbn}{anb**n}, 正则语言闭包

Instantaneous Description（瞬时描述）

Instantaneous Description（ID） 是 形式语言与自动机理论 中的一个核心概念，用于描述自动机（如下推自动机、图灵机等）在 某一瞬间 的完整状态。它记录了自动机的当前状态、剩余输入字符串和栈（或纸带）的内容，是分析自动机运行过程的重要工具。

---

核心组成

一个 ID 通常表示为三元组： $(q, w, \gamma)$

• ( q )：自动机当前所处的状态。
• ( w )：尚未处理的 剩余输入字符串。
• ($ \gamma $)：栈顶到栈底的符号序列（对下推自动机）或纸带内容（对图灵机）。

---

应用场景

下推自动机（PDA）

• 例如，PDA 处理字符串 aabb 时，ID 的变化可能如下：
  $ (q_0, aabb, Z_0) \vdash (q_1, abb, AZ_0) \vdash (q_1, bb, AAZ_0) \vdash (q_2, b, AZ_0) \vdash (q_2, \epsilon, Z_0) $
• 每一步表示状态、输入和栈的同步变化。

关键作用

• 追踪计算过程：通过 ID 序列可逐步分析自动机如何接受或拒绝输入。
• 证明自动机等价性：例如证明两个自动机接受同一语言时，需构造 ID 的双向映射。
• 非确定性路径分析：在非确定型自动机（如 NPDA）中，ID 表示所有可能的并行计算路径。

CFG = PDA

Properties of CFL

Pumping Lemma for CFL

期末再来学吧

• 编译原理