CFGs和pda是等效的
当且仅当某些PDA接受语言L时，语言L是由CFG生成的。
因为这是一个当且仅当定理我们必须从两个方向证明它。我将把它分成两个证明。
上半年
如果某些PDA接受语言L，则存在生成L的无关上下文的语法。
首先，我们对PDA进行标准化：
- 添加一个新的符号#到堆栈字母表。
- 为PDA创建一个新的启动状态，并添加从新的启动状态到旧的启动状态的转换。
- 如果原始PDA接受一些输入而不清空其堆栈，则修改接受状态以清空堆栈。
- 如果PDA有多个接受状态，请将赢博体育接受状态转换为常规状态，并添加如下所示的转换，以将以前的接受状态连接到新的接受状态。
- 如果PDA中的任何过渡既弹出一个符号又在同一过渡上推送一个符号（例如a，b→c），则将其替换为
现在，假设PDA的开始状态为s，唯一接受状态为f，我们创建一组语法规则：
年代→,f
Ap,p→ε
Ap q→Ap r Ar q
后一种规则是为Q×Q×Q中赢博体育可能的三元组（p,r,q）创建的。
最后，对于每一对状态p和q都有这样的转换
添加语法规则
Ap q→a Ar t b
现在，设x为PDA接受的任意字符串。我们认为我们刚刚创建的语法可以生成x。为了做到这一点，我们证明了一些更一般的东西：
引理x可以将PDA从带空堆栈的状态p带到带空堆栈的状态q当且仅当Ap q生成x。
第一部分证明
如果x可以把PDA从状态p和一个空的堆栈带到状态q和一个空的堆栈那么Ap q产生x
证明是通过归纳法对从p到q的过渡次数进行的。
基本情况：如果从p到q的路径长度为0，则PDA没有机会读取任何输入符号。因此，x = ε, p = q。语法规则Ap，p→ε产生x。
归纳步骤：假设从p到q的路径有n个步骤。如果路径上第一步推入的符号与最后一步弹出的符号相同，且x的形式为ayb，则x求导的第一条规则为Ap，q→a Ar,t b。从r到t的路径需要n-2步，因此根据归纳假设Ar，t可以生成y，我们有Ap，q→a Ar,t b⇒ayb = x
如果在从p到q的路径上第一个被推入的符号和最后一个被弹出的符号不一样，那么在这个路径上就会有一个状态r，在这个状态r中，第一个被推入的符号再次被弹出。在这种情况下，步骤Ap q→Ap r Ar q是x = yz求导的第一步。因为从p到r和从r到q的路径都比从p到q的路径短，归纳假设告诉我们Ap，r推导出y， Ar，q推导出z，我们有Ap，q→Ap,r Ar,q⇒y Ar,q⇒y z = x。
证明第二部分
如果Ap，q产生x，那么x可以将PDA从具有空堆栈的状态p带到具有空堆栈的状态q。
证明是通过对x求导的步数进行归纳法。
基本情况：如果x的推导只包含一个步骤，那么这个步骤必须是Ap，p→ε。在这种情况下p = q, x = ε。机器中肯定有一条从状态p到状态p的路径，它什么也没读。
归纳步骤：考虑从Ap，q推导x的第一步。第一步有两种可能。
如果它的形式是Ap q→Ap r Ar，我们设y是由Ap导出的弦，设z是由Ar导出的弦。这两个子推演的步骤都比x的推演少，所以归纳假设允许我们说y将机器从状态p的空堆栈带到状态r的空堆栈，而z将机器从状态r的空堆栈带到状态q的空堆栈。因此，x = yz将机器从具有空堆栈的状态p带到具有空堆栈的状态q。
如果推导的第一步采用Ap，q→a, Ar,t， b的形式，我们看到机器可以从读取a开始，并在堆栈上压入一些东西，然后读取b，同时从堆栈中取出相同的东西。这告诉我们x = ay b。同样，我们看到Ar，t推导出y。因为这个推导必然比x的推导短，归纳假设允许我们说机器可以把我们从状态r和空堆栈带到状态t和空堆栈。把这些放在一起，我们现在看到x把我们从状态p和一个空的堆栈带到状态q和一个空的堆栈。
下半年
定理如果L是CFL，则存在一个接受L的PDA。
下图显示了PDA的结构：
规则循环是循环的集合，每个语法规则对应一个循环。例如，如果语法包含规则
故选B
机器将包含一个循环，看起来像这样：
循环从堆栈中弹出一个A，然后将规则右侧的项以相反的顺序推入堆栈。确保右边的第一项位于堆栈的顶部，并可用于下一个操作。
终端循环将位于堆栈顶部的终端与从输入端进入的同一终端相匹配。
这台机器通过猜测输入字符串的派生来工作。如果机器能够猜出正确的推导，并最终通过使用终端循环匹配输入的每个字符，那么机器可以到达具有空堆栈的最终状态。