Clever Geek Handbook

Create a PDA of all lines 0 and 1 so that the number 1 is twice the number 0

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

The PDA should accept a string in which the number of numbers 1 is equal to the binary number 0, and if I am not misinterpreting the question, the string may have a different sequence of 0s and 1s without a particular pattern or particular order.

My first approach to this problem was to split the problem into two parts

  • PDA for lines starting with 0. (Example - 010111)
  • PDA for lines starting with 1. (Example - 110101)

But dividing the problem does not diminish the complexity of the problem.

What should be the approach to such problems?

+3


source to share


3 answers


It doesn't matter if the line starts with 0 or 1, what to keep in mind when solving this problem is that we have to push one 1 for every two 1s above the stack if the top of the stack is 1 and similarly if we are facing 0 as the stack on top, then we have to pop it only when the second row 1 appears on the line. This motive can be easily achieved through two states. Let the states be q0 and q1. If we are in the q0 state, then this means that we have not encountered the first 1 pair, and from the q1 state it follows that we have already encountered the first 1 pair. The various transitions for the PDA are shown below.

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

+6


source


The idea is this:

Pop two 1 for each 0 or press two 0 for each 0.



Put one 0 for each 1, or press one on 1 for each.

0


source


It is necessary to add two more states with this 𝛿 (q1,0, z) = {(q1, 0z)} and

𝛿 (q1,1, z) = {(q1, 1z)}. Also, to improve the answer, keep a separate final state, that is, 𝛿 (q0, ε, z) = {(qf, ε)}, where qf is the final state. To check the correctness, the following lines can be used (111100, 001111, 110110, 101110, 100111, 101011, etc.)

0


source






More articles:


All Articles