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

Question

在为我的期末考试练习时,我在J. Hopcroft,R.Motwani,J.Ullman,第222页的自动机理论,语言和计算中发现了这个问题.

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

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

1. 用于从0开始的字符串的PDA.(例如 - 010111)
2. 用于以1开头的字符串的PDA.(例如 - 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)}

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

Answer 2

想法如下：

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

每有 1 就弹出 1 个 0，或者每有 1 就压入 1 个 1。