
- 自动机理论教程
- 自动机理论 - 首页
- 自动机理论 - 入门
- 自动机理论 - 历史
- 自动机理论 - 应用
- 自动机理论术语
- 自动机中字符串的基础知识
- 自动机的集合论
- 语言和文法
- 计算理论中的文法
- 由文法生成的语言
- 乔姆斯基文法分类
- 有限自动机
- 确定性有限自动机 (DFA)
- 非确定性有限自动机 (NFA)
- 从 NFA 到 DFA 的转换
- DFA 的最小化
- Moore 机与 Mealy 机
- DFA 的补集
- 正则表达式
- 自动机中的正则表达式
- 自动机中的 Arden 定理
- 将正则表达式转换为有限自动机
- 正则文法的泵引理
- 计算理论中的正则集
- 上下文无关文法
- 上下文无关文法 (CFG)
- 上下文无关文法中的二义性
- 上下文无关语言的封闭性
- 简化上下文无关文法
- 乔姆斯基范式 (CNF)
- 格雷巴赫范式 (GNF)
- 上下文无关文法的泵引理
- 下推自动机
- 下推自动机 (PDA)
- 下推自动机接受
- 从 CFG 构造 PDA
- 下推自动机和解析
- 图灵机
- 图灵机 (TM) 基础
- 图灵机接受的语言
- 多磁带图灵机
- 多轨迹图灵机
- 非确定性图灵机
- 半无限磁带图灵机
- 线性有界自动机 (LBA)
- 可计算性和不可判定性
- 图灵语言的可判定性
- 不可判定语言
- 图灵机停机问题
- 计算理论中的 Rice 定理
- Post 对应问题 (PCP)
- 自动机理论资源
- 自动机理论 - 快速指南
- 自动机理论 - 资源
- 自动机理论 - 讨论
下推自动机接受
有两种不同的方法可以定义 PDA 的可接受性。
最终状态可接受性
在最终状态可接受性中,当 PDA 读取完整个字符串后处于最终状态时,PDA 接受一个字符串。从起始状态,我们可以进行最终状态的移动,并带有任何堆栈值。只要我们最终处于最终状态,堆栈值就无关紧要。
对于 PDA (Q, ∑, S, δ, q0, I, F),由最终状态集 F 接受的语言是:
L(PDA) = {w | (q0, w, I) ⊢* (q, ε, x), q ∈ F}
对于任何输入堆栈字符串x。
空堆栈可接受性
在这里,当 PDA 读取完整个字符串后清空其堆栈时,PDA 接受一个字符串。
对于 PDA (Q, ∑, S, δ, q0, I, F),由空堆栈接受的语言是:
L(PDA) = {w | (q0, w, I) ⊢* (q, ε, ε), q ∈ Q}
示例
构造一个接受L = {0n 1n | n ≥ 0}的 PDA
解答

此语言接受 L = {ε, 01, 0011, 000111, ............................. }
在这里,在这个例子中,‘0’ 和 ‘1’ 的数量必须相同。
最初,我们将一个特殊的符号‘$’放入空堆栈中。
然后在状态q2,如果我们遇到输入 0 并且顶部为空,我们将 0 推入堆栈。这可能会迭代。如果我们遇到输入 1 并且顶部是 0,我们将弹出此 0。
然后在状态q3,如果我们遇到输入 1 并且顶部是 0,我们将弹出此 0。这也可能会迭代。如果我们遇到输入 1 并且顶部是 0,我们将弹出顶部元素。
如果在堆栈顶部遇到特殊符号 '$',则将其弹出,最终进入接受状态 q4。
示例
构造一个接受 L = { wwR | w = (0+1)* } 的 PDA
解答

最初,我们将一个特殊的符号 '$' 放入空堆栈中。在状态q2,正在读取w。在状态q3,当每个 0 或 1 与输入匹配时,它会被弹出。如果给出任何其他输入,PDA 将进入死状态。当我们到达特殊符号 '$' 时,我们将进入接受状态q4。