在为我的期末考试练习时，我在J. Hopcroft、R. Motwani、J. Ullman 的 Automata Theory, Language and Computation中发现了这个问题，第 222 页。
PDA 应该接受其中 1 的数量是 0 数量的两倍的字符串，如果我没有误解这个问题，那么该字符串可以有不同的 0 和 1 序列，没有特定的模式或特定的顺序。
我解决这个问题的第一个方法是将问题分成两部分
但是划分问题似乎并没有降低问题的复杂性。
解决此类问题的方法应该是什么？
字符串以 0 还是 1 开头并不重要，在解决这个问题时应该牢记的是，如果栈顶为 1 和类似情况，我们将为每两个 1 压入一个 1，如果我们遇到 0 作为堆栈顶部，那么我们必须仅在字符串中出现第二个 1 时将其弹出。通过使用两种状态可以很容易地实现这个动机。让状态为 q0 和 q1。如果我们处于 q0 状态，那么这意味着我们还没有遇到这对中的第一个 1，而状态 q1 意味着我们已经遇到了这对中的第一个 1。PDA 的各种转换如下所示。
设 PDA 为 P({q0, q1},{0, 1},{0,1,z},,q0,z)
(q0,0,z) = {(q0, 0z)}
(q0,1,z) = {(q1, z)}
(q0,0,0) = {(q0, 00)}
(q0,1,0) = {(q1, 0)}
(q0,0,1) = {(q0, ε)}
(q0,1,1) = {(q1,1)}
(q1,0,0) = {(q1, 00)}
(q1,1,0) = {(q0, ε)}
(q1,0,1) = {(q1,ε)}
(q1,1,1) = {(q0, 11)}
(q1,0,z) = {(q1, 0z)}
(q1,1,z) = {(q1, 1z)}
(q0,ε,z) = {(q0, ε)}
我知道这已经 5 岁了，但是由于没有接受答案，我想我会分享我的答案，看看它是否对任何人有帮助（我确信它可以简化，但这是我的逻辑）：
PDA定义：P({S, M, Z, q1, F}, {0, 1}, {0, 1, $},下面描述的转移函数, S, {S, F})
我在下面插入了我的绘图图片，但我首先将 $ 压入堆栈以指示底部并进入状态 M。然后，如果第一个符号是零，则将零压入堆栈并进入状态z。如果是 1，则将 1 压入堆栈并进入状态 q1。在状态 z 中，如果字符串中的下一个零，则停留在状态 z 并将零添加到堆栈中。如果字符串中的下一个 1 并且堆栈顶部有一个零，则将零从堆栈中弹出并停留在状态 z 中。如果在状态 z 中字符串中的下一个 1 并且堆栈为空，则移动到状态 q1 并将 1 压入堆栈。如果字符串为空并且堆栈顶部有一个 $，则弹出 $ 并进入状态 F。
状态 q1 具有几乎相同的转换，但相反。
在状态 q1 中，如果字符串中的下一个是 1，则保持状态 q1 并将 1 添加到堆栈中。如果字符串中的下一个零并且堆栈顶部有一个 1，则将 1 从堆栈中弹出并保持状态 q1。如果在状态 q1 中的字符串中的下一个 0 并且堆栈为空，则移动到状态 z 并将 0 压入堆栈。如果字符串为空并且堆栈顶部有一个 $，则弹出 $ 并进入状态 F。
这个逻辑如下图所示。
还需要添加两个状态 (q1,0,z) = {(q1, 0z)} 和
(q1,1,z) = {(q1, 1z)}。此外，为了改进答案，保留一个单独的最终状态，即 (q0,ε,z) = {(qf, ε)} 其中，qf 是最终状态。要检查有效性，可以使用以下字符串（111100、001111、110110、101110、100111、101011 等）
包含相同数量的零和
一的语言的语法是S -> 0S1S | 1S0S | epsilon
类似地，包含两倍于 0 的 1 数量的语言的语法是
S -> 0S1S1S | 1S0S1S | 1S1S0S | epsilon
所以 NPDA 将类似于：
从 q0 到 q1：如果您阅读epsilon并看到z堆栈顶部，则 push S。
从 q1 到 q1：如果您阅读epsilon并看到 S 在堆栈顶部，则 push0S1S1S或 push1S0S1S或 push1S1S0S或 pop。如果您阅读0并看到0堆栈顶部，则弹出。如果您阅读1并看到1堆栈顶部，则弹出。
从 q1 到 q2：如果您阅读epsilon并看到z堆栈顶部，则弹出。q2 是最终状态。
思路如下：
每个 0 弹出两个 1 或每个 0 压入两个 0。
每个 1 弹出一个 0 或每个 1 压入一个 1。