draw the pushdown automaton

Question

How can I draw the pushdown automaton for language $L = \{ bin(n) \text{#} bin(3n)^{R} | n \in \mathbb{Z}, n \geq 0 \}$ when bin(n) is binary notation of $n$ without leading zeros. Alphabet is $\{ 0, 1, \text{#} \}$

Answer 1

Design it to mimic ordinary long multiplication by $3$ in binary. I’ll outline what’s needed.

The key is to recognize that multiplying a binary number by $3$ is just adding the number to the result of shifting it one place to the left, as in this example of $185\cdot3$:

            10111001
                  11
            --------
            10111001
           10111001
           ---------
          1000101011

The automaton should stack the input until it reads a $\#$. At that point the top element of the stack will be the least significant bit of $n$. If the input is in $L$, that bit should agree with the next bit of input. The basic processing cycle from this point on is:

• Use the bit at the top of the stack and the current state to determine what the next bit of input ought to be and whether there should be a carry into the next ‘column’;
• If the next input bit is correct, pop one bit off the stack and go to one of four states, depending on the popped bit, the present state, and whether or not there is a carry to the next ‘column’. The states keep track of whether the popped bit was $0$ or $1$ and whether there is an outgoing carry.

Of course if the next input bit is not correct, the input is not in $L$.

Answer 2

Here is how our PDA works :

1. if the first symbol is not 1 reject (except if the string is # , see edge cases down)
2. push all symbols to stack till you read # , do not push # (this step is pushing all symbols of bin(n) to stack)
3. now using the stack we can read bin(n) from right to left , the input we receive from this point is supposed to be bin(3n)^r , meaning we can read also bin(3n) from right to left
4. Now we consider the symbol at top of stack x , the symbol we read w , and make transitions for valid x & w to states that correspond to the carry
5. ex 1, after reading # , if x = 0 , 0*3 = 0 , carry = 0 , so if x = 0 , we expect w = 0 , and we head to state carry = 0 , that is 0,0;ε to carry 0
6. ex 2, if we are in state carry 1 , and x = 0 , 0*3 + 1 = 1 and carry = 0 , so if x = 0 , and we are in carry 1 , we expect w = 1 , and we go to state carry = 0 , that is 1,0;ε to carry 0
7. Now continue this way and you should be able to construct the PDA , you will find that you will need another state for carry 2 , for each state think about valid x & w to make a transition and what carry will they cause to know which state you will head to , continue this way till you finish the PDA
8. if we are in state carry 0 , and stack is empty , we non-deterministically guess that input has finished and head to accept state

Hopefully these steps help you build your own PDA , after you try , you can check your answer , here is the PDA :

edge cases :

here we explain how the transition 1,\$;\$ acts like 1,0;ε for ex : if bin(n) = 1 , you see how bin(3n) = 10 , bin(3n)^r = 01 , after reading bin(n) the stack will have \$1 after reading 0 from bin(3n)^r the stack will be $ and we are in carry 1 , usually we need to pop a 0 to go to carry 0 , but since we read \$ , we know this is the end of bin(n) and so we treat \$ as if it was a leading 0 ( which does not change bin(n) ) , we pop \$ as if we would have popped a 0 , then push it again for the test of emptiness of stack , if you think about it you can make the same transition to the accept state instead of carry 0 , both are the same

in case n = 0 , bin(0) = 0 , since we do not allow leading 0s , the string will end up being just # , so we guess whether n = 0 or not , if n is not 0 we check if b(n) starts with 1