证明正则语言集合是上下文无关语言集合的真子集
我正在温习（不是家庭作业）一些计算理论，并遇到了这个问题：
如何证明常规语言集是上下文无关语言集的真子集。
现在我知道一种语言是正规的，当且仅当它被有限自动机接受。
我知道一种语言是上下文无关的，当且仅当它被下推接受 自动机。
但我不确定解决方案是什么。
I was brushing up (not homework)on some computation-theory and came accross this problem:
How can you prove that the set of regular languages is a proper subset of the set of the context-free languages.
Now I know a language is regular iff it is accepted by a finite automaton.
And I know a language is context-free iff it is accepted by a pushdown
automaton.
But I'm not sure of what solution is.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
任何 DFA 都相当于 PDA，它永远不会将任何内容推送到其堆栈上，因此所有常规语言也是上下文无关的。更正式地说：
DFA 被定义为 5 元组 (Σ,S,s0,δ,F)，由输入字母表、状态集、
开始状态、转换表和最终（接受）状态集。
PDA 被定义为 7 元组，包括 DFA 的所有元素，加上两个附加参数： Γ（堆栈字母表）和 Z（初始堆栈符号）。 PDA 转换表与 DFA 转换表有些不同：每个转换可以依赖于
输入符号和当前堆栈符号，并且转换可以压入或弹出
从堆栈中。
因此，通过引入由单个符号组成的虚拟堆栈字母表，映射 DFA 转换表是微不足道的（尽管写起来有点烦人且冗长！）
（状态，输入）->状态到等效的PDA转换表（状态，输入，堆栈）-> （状态，堆栈）。完成真子集关系的证明：存在上下文无关语言，但不是正则语言，因此正则语言构成上下文无关语言的真子集。示例：由平衡括号组成的字符串语言。
Any DFA is equivalent to a PDA which happens to never push anything onto its stack, therefore all regular languages are also context-free. More formally:
A DFA is defined as a 5-tuple (Σ,S,s0,δ,F) consisting of the input alphabet, set of states,
start state, transition table, and set of final (accepting) states.
A PDA is defined as a 7-tuple, including all the elements of a DFA, plus two additional parameters: Γ (the stack alphabet), and Z (the initial stack symbol). A PDA transition table is somewhat different from a DFA transition table: each transition can depend on
both the input symbol and current stack symbol, and the transitions may push or pop
from the stack.
So by introducing a dummy stack alphabet consisting of a single symbol, it's trivial (though somewhat annoying and long-winded to write out!) to map the DFA transition table
(state, input) -> stateto an equivalent PDA transition table(state, input, stack) -> (state, stack).To complete the proof of a proper subset relationship: there exist languages which are context-free, but not regular, so the regular languages form a proper subset of the context-free languages. Example: the language of strings consisting of balanced parentheses.