我正在复习（不是家庭作业）一些计算理论并遇到了这个问题：
您如何证明常规语言集是上下文无关语言集的适当子集。
现在我知道一种语言是规则的，如果它被有限自动机接受。
而且我知道一种语言是无上下文的，前提是它被下推自动机接受。
但我不确定解决方案是什么。
问问题
3268 次
1 回答
2
任何 DFA 都相当于一个 PDA，它碰巧从不将任何东西压入其堆栈，因此所有常规语言也是上下文无关的。更正式地说：
DFA 定义为 5 元组 (Σ,S,s0,δ,F)，由输入字母表、状态集、开始状态、转换表和最终（接受）状态集组成。
PDA 被定义为一个 7 元组，包括 DFA 的所有元素，加上两个附加参数：Γ（堆栈字母）和 Z（初始堆栈符号）。PDA 转换表与 DFA 转换表有些不同：每个转换都可以依赖于输入符号和当前堆栈符号，并且转换可以从堆栈中压入或弹出。
(state, input) -> state因此，通过引入由单个符号组成的虚拟堆栈字母表，将 DFA 转换表映射到等效的 PDA 转换表是微不足道的（尽管写出来有些烦人和冗长！）
(state, input, stack) -> (state, stack)。
完成真子集关系的证明：存在上下文无关的语言，但不是正则的，因此正则语言形成了上下文无关语言的一个真子集。示例：由平衡括号组成的字符串语言。
于 2011-01-10T23:52:14.130 回答