Design a PDA of all strings of 0's and 1's so that the number of 1's is twice the number of 0's

Question

While practicing for my final exams I found this question in Automata Theory, Language and Computation by J. Hopcroft, R. Motwani, J. Ullman on page 222.

PDA should accept string in which the count of number of 1's is twice of number of 0's and if I'm not misinterpreting the question, the string can have different sequence of 0's and 1's in no particular pattern or specific order.

My first approach to this problem was to divide the problem in two parts

1. PDA for strings starting with 0. (For Example - 010111)
2. PDA for strings starting with 1. (For Example - 110101)

But dividing the problem don't seems to reduce the complexity of the problem.

What should be ones approach to such problems?

Answer 1

It doesn't matter whether the string starts with 0 or 1, the thing that should be kept in mind while solving this problem is that, we are to push a single 1 for every two 1's over stack, if stack top is 1 and similarly, if we encounter 0 as stack top then we have to pop it only on the occurrence of second 1 in string. This motive can easily be achieved by using two states. Let the states be q0 and q1. If we are in q0 state then it implies that we haven't encountered the first 1 of the pair and the state q1 implies that we have already encountered the first 1 of the pair. Various transitions for PDA are shown below.

Let the PDA be 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, ε)}