6

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?

user3276435
  • 265
  • 1
  • 3
  • 13

5 Answers5

11

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

user3915636
  • 23
  • 4
Dilraj Singh
  • 131
  • 1
  • 8
  • 1
    how will 1 get into the stack? all the push of 1 to the stack are happening when 1 is already on the stack top – Shantanu Shinde Oct 17 '19 at 03:39
  • But this does not work. Test it wih 110. It ends in (q1, z) – David Davó Apr 14 '20 at 16:24
  • Given that your PDA is a sextuple, without a set of final states, I assume it accepts strings with a null stack, regardless of the state the computation ends in. For the input string `1`, using `(q0,1,z) = {(q1, z)}`, we get to state q1. Our stack is empty, so the string will be accepted. I believe changing the transition to `(q0,1,z) = {(q1, 1z)}` will work. – aryan May 14 '22 at 21:48
1

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.

My drawing of the PDA

Unheilig
  • 16,196
  • 193
  • 68
  • 98
Hmkyriacou
  • 64
  • 1
  • 8
0

Two more states need to be added with this (q1,0,z) = {(q1, 0z)} and

(q1,1,z) = {(q1, 1z)}. Moreover, to improve the answer keep a separate final state, i.e. (q0,ε,z) = {(qf, ε)} where, qf is the final state. To check the validity, one can use the following strings (111100, 001111, 110110, 101110, 100111, 101011 etc. )

user3915636
  • 23
  • 4
0

The grammar for a language containing the same number of zeros and ones is S -> 0S1S | 1S0S | epsilon

Similarly, the grammar for a language containing twice the number of 1s as 0s is S -> 0S1S1S | 1S0S1S | 1S1S0S | epsilon

So the NPDA will be something like:

From q0 to q1: If you read epsilon and see z at the top of the stack, push S.

From q1 to q1: If you read epsilon and see S at the top of the stack, push 0S1S1S or push 1S0S1S or push 1S1S0S or pop. If you read 0 and see 0 at the top of the stack, pop. If you read 1 and see 1 at the top of the stack, pop.

From q1 to q2: If you read epsilon and see z at the top of the stack, pop. q2 is the final state.

arunkumaraqm
  • 337
  • 1
  • 13
-1

The idea is as follows:

Pop two 1's for each 0 or push two 0's for each 0.

Pop one 0 for each 1 or push one 1 for each 1.

Hassan Abbasi
  • 272
  • 1
  • 3