证明普通语言集是无上下文语言集的正确子集

Question

我在某些计算理论上刷了（不是作业），并遇到了这个问题：

您如何证明普通语言集是无上下文语言集的适当子集。

现在，我知道语言是常规的，如果是有限的自动机接受。

而且我知道语言是不含上下文的，如果它被下降自动机接受。

但是我不确定什么是解决方案。

Answer 1

任何DFA都等同于PDA，它恰好从未将任何内容都推到其堆栈上，因此所有普通语言也不上下文。更正式：

DFA定义为由输入字母，一组状态，启动状态，过渡表和最终（接受）状态的集合组成的5核（σ，S，S0，δ，F）。

PDA定义为7核，包括DFA的所有元素，以及两个附加参数：γ（堆栈字母）和Z（初始堆栈符号）。 PDA过渡表与DFA过渡表有所不同：每个过渡都可以取决于输入符号和当前堆栈符号，并且过渡可能会从堆栈中推出或弹出。

因此，通过引入一个由单个符号组成的虚拟堆栈字母，它是微不足道的（尽管有些烦人和漫长的书写！）来映射DFA过渡表(state, input) -> state 到等效的PDA过渡表 (state, input, stack) -> (state, stack).

为了完成适当的子集关系的证明：存在无上下文的语言，但不是规则的语言，因此普通语言构成了无上下文语言的适当子集。示例：由平衡括号组成的字符串语言。