automata - 设计一个包含 0's and 1' 的所有字符串的 PDA，使得 1's is twice the number of 0' 的数量

Question

在准备期末考试时，我在 J. Hopcroft、R. Motwani、J. Ullman 的《自动机理论、语言和计算》第 222 页上发现了这个问题。

PDA 应该接受其中 1 的数量是 0 数量的两倍的字符串，如果我没有误解这个问题，该字符串可以有不同的 0 和 1 序列，没有特定的模式或特定的顺序。

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

1. PDA 用于以 0 开头的字符串。(例如 - 010111)
2. PDA 用于以 1 开头的字符串。(例如 - 110101)

但是划分问题似乎并没有降低问题的复杂性。

解决此类问题的方法是什么？

Answer 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, ε)}