设计一个包含所有0和1字符串的PDA，使1的数量是0数量的两倍

Question

在准备期末考试时，我在 J. Hopcroft、R. Motwani、J. Ullman 的《自动机理论、语言和计算》第 222 页中发现了这个问题。 PDA 应该接受其中 1 的数量是 0 数量的两倍的字符串，如果我没有误解这个问题，该字符串可以有不同的 0 和 1 序列，没有特定的模式或特定的顺序。

我解决这个问题的第一个方法是将问题分为两部分

PDA 用于以 0 开头的字符串。（例如 - 010111）

1. PDA 用于以 1 开头的字符串。（例如 - 110101）
但是划分问题似乎并没有降低问题的复杂性。

应对此类问题应该采取什么方法？

Answer 1

堆栈上每两个1压入一个1

，如果堆栈顶部是1 类似地，如果我们遇到 0 作为栈顶，那么我们必须仅在字符串中出现第二个 1 时才将其 pop 。通过使用两种状态可以轻松实现此动机。令状态为 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) = {(q0, 1z)}

𝛿(q0,ε,z) = {(q0, ε)}

（第二次转换已于 2023 年 3 月 6 日从 𝛿(q1,1,z) = {(q1, 1z)} 更新为 𝛿(q1,1,z) = {(q0, 1z)}）

我知道这已经有5年历史了，但由于答案尚未被接受，我想我会分享我的答案，看看它是否对任何人有帮助（我确信它可以简化，但这是我的逻辑）：

Answer 2

PDA定义：P({S, M, Z, q1, F}, {0, 1}, {0, 1, $},

下面描述的转换函数

, S, {S, F}) 我在下面插入了我的绘图图片，但我所做的是首先将 $ 压入堆栈以指示底部并进入状态 M。然后，如果第一个符号是零，则将零压入堆栈并进入状态 M状态 z。如果是 1，则将 1 压入堆栈并进入状态 q1。在状态 z 中，如果字符串中的下一个是零，则保持在状态 z 并向堆栈添加一个零。如果字符串中的下一个是 1，并且堆栈顶部有一个零，则将零从堆栈中弹出并保持在状态 z。如果状态 z 的字符串中的下一个是 1 并且堆栈为空，则移动到状态 q1 并将 1 压入堆栈。如果字符串为空并且堆栈顶部有 $，则弹出 $ 并进入状态 F。

状态 q1 具有几乎相同的转换，除了相反之外。

在状态 q1 中，如果字符串中的下一个是 1，则保持在状态 q1 并将 1 添加到堆栈中。如果字符串中的下一个是 0，并且堆栈顶部有一个 1，则将 1 从堆栈中弹出并保持在状态 q1。如果状态 q1 中的字符串中的下一个是 0 并且堆栈为空，则移动到状态 z 并将 0 压入堆栈。如果字符串为空并且堆栈顶部有 $，则弹出 $ 并进入状态 F。

这个逻辑如下图所示。

还需要添加两个状态 𝛿(q1,0,z) = {(q1, 0z)} 和

Answer 3

𝛿(q1,1,z) = {(q1, 1z)}。此外，为了改进答案，请保留单独的最终状态，即 𝛿(q0,ε,z) = {(qf, ε)} 其中，qf 是最终状态。要检查有效性，可以使用以下字符串（111100、001111、110110、101110、100111、101011 等）

包含“相同”数量的 0 和 1 的语言的语法是

Answer 4

类似地，包含两倍于 0 数量的 1 的语言的语法是 S -> 0S1S1S | 1S0S1S | 1S1S0S | epsilon

所以 NPDA 会是这样的：

从 q0 到 q1：如果您读到 

epsilon

并在堆栈顶部看到

z

，请推入

S

。

从 q1 到 q1：如果您读到 

epsilon

 并看到 S 在堆栈顶部，则压入 

0S1S1S

或压入

1S0S1S

 或压入 

1S1S0S

 或弹出。如果您读到 

0

 并在堆栈顶部看到 

0

，请弹出。如果您阅读 

1

 并在堆栈顶部看到 

1

，请弹出。

从 q1 到 q2：如果您读到 

epsilon

 并看到堆栈顶部有 

z

，则弹出。 q2 是最终状态。

想法如下：

为每个 0 弹出两个 1，或者为每个 0 压入两个 0。

Answer 5

每 1 弹出一个 0 或每 1 压入 1。