问证明了正则语言集是上下文无关语言集的真子集

EN

任何DFA都等同于一个PDA，它碰巧永远不会把任何东西推到它的堆栈上，因此所有的常规语言也是上下文无关的。更正式地说：

DFA被定义为由输入字母表、状态集、开始状态、转换表和最终(接受)状态集组成的5元组(Σ，S，s0，δ，F)。

PDA被定义为一个7元组，包括DFA的所有元素，外加两个附加参数:Γ(堆栈字母表)和Z(初始堆栈符号)。PDA转换表与DFA转换表有些不同:每个转换都可以依赖于输入符号和当前堆栈符号，并且转换可以从堆栈推出或弹出。

因此，通过引入一个由单个符号组成的虚拟堆栈字母表，它是微不足道的(尽管写出来有点烦人和冗长！)以将DFA转换表(state, input, stack) -> (state, stack)映射到等效的PDA转换表PDA。

为了完成一个适当子集关系的证明:存在上下文无关但不是正则的语言，因此正则语言构成了上下文无关语言的真子集。示例:由对括号组成的字符串的语言。