证明了正则语言集是上下文无关语言集的真子集
证明了正则语言集是上下文无关语言集的真子集
提问于 2011-01-10 23:48:39
我正在复习一些计算理论(而不是作业)，遇到了这个问题：
如何证明正则语言集是上下文无关语言集的真子集呢？
现在我知道一种语言是正则的当且仅当它被有限自动机所接受。
我知道一种语言是上下文无关的，如果它被下推自动机所接受。
但我不确定解决方案是什么。
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-01-10 23:52:14
任何DFA都等同于一个PDA，它碰巧永远不会把任何东西推到它的堆栈上，因此所有的常规语言也是上下文无关的。更正式地说：
DFA被定义为由输入字母表、状态集、开始状态、转换表和最终(接受)状态集组成的5元组(Σ，S，s0，δ，F)。
PDA被定义为一个7元组，包括DFA的所有元素，外加两个附加参数:Γ(堆栈字母表)和Z(初始堆栈符号)。PDA转换表与DFA转换表有些不同:每个转换都可以依赖于输入符号和当前堆栈符号，并且转换可以从堆栈推出或弹出。
因此，通过引入一个由单个符号组成的虚拟堆栈字母表，它是微不足道的(尽管写出来有点烦人和冗长！)以将DFA转换表(state, input, stack) -> (state, stack)映射到等效的PDA转换表PDA。
为了完成一个适当子集关系的证明:存在上下文无关但不是正则的语言，因此正则语言构成了上下文无关语言的真子集。示例:由对括号组成的字符串的语言。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/4652839
复制相关文章
相似问题
证明了CFG和正则语言的集合差异也是上下文无关的
非正则上下文无关语言与无限正则子语言
上下文无关语言的子集是可决定的吗？
上下文无关语言的一个子集是上下文无关吗？
上下文无关语言是否是确定性上下文无关语言
添加站长 进交流群
领取专属 10元无门槛券
AI混元助手 在线答疑
关注 腾讯云开发者公众号
洞察 腾讯核心技术
剖析业界实践案例
腾讯云开发者
