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

Answer 2

I know this is 5 years old, but since an answer has not been accepted, I figured I would share my answer and see if it helped anyone (I'm sure it can be simplified but this was my logic):

PDA definition: P({S, M, Z, q1, F}, {0, 1}, {0, 1, $}, Transition function described below, S, {S, F})

I inserted a picture of my drawing below but what I did was first push a $ onto the stack to indicate the bottom and move into state M. Then, if the first symbol was a zero, push a zero onto the stack and move into state z. If it was a one, push a 1 onto the stack and move into state q1. In state z, if a zero is next in the string, stay in state z and add a zero onto the stack. If a 1 is next in the string and there is a zero on the top of the stack, pop the zero off the stack and stay in state z. If a 1 is next in the string in state z and the stack is empty then move to state q1 and push a 1 onto the stack. If the string is empty and there is a $ on top of the stack then pop the $ and move into state F.

State q1 has nearly the same transitions except opposite.

In state q1, if a one is next in the string, stay in state q1 and add a one onto the stack. If a zero is next in the string and there is a 1 on the top of the stack, pop the 1 off the stack and stay in state q1. If a 0 is next in the string in state q1 and the stack is empty then move to state z and push a 0 onto the stack. If the string is empty and there is a $ on top of the stack then pop the $ and move into state F.

This logic is drawn out in the below picture.