Show that this language is context-free by giving a pushdown automaton

Question

I have to show that the language L is context-free by drawing the pushdown automaton.

L = $x\$y^r$: where x is the binary representation of an integer nx and y represents the integer nx+ 1

$y^r$ represents the word y reversed.

So example : $10010\$11001$ is in T because $10010 = 18$ and $y^r = 10011$ which is equal to 19

So I have started a drawing which is not finished because I am stuck:

From there I am a bit stuck on how to handle the part after the $.

I understand that $y^r$ is $x^r + 1$ but I can't seem to find a way to illustrate it in the pushdown automaton

Thanks for your help. Here's the tool I use to draw if u wanna help out: http://madebyevan.com/fsm/

Answer 1

ok lets consider a string x , we have 2 cases :

1. x ends with a 0 :

for ex , x = 1010 , x+1 = 1010 + 1 = 1011

so in this case , clearly y is the same as x , except for the last symbol

so , if the last symbol in x , that is the top of the stack after pushing all symbols of x , if it is 0 , we need to make sure that the first symbol in y^r (which is the last symbol in y ) is 1 , then we need to make sure all other symbols match x ,

2. x ends with a 1 :

for ex , x = 1011 , x+1 = 1011 + 1 = 1100 , what happened here ?

if the last symbol in x is 1 , then in y , starting from least significant bit (rightmost symbol) , all 1s become 0s , then the first 0 we encounter becomes a 1 , the rest of the string remains the same , this is due to adding 1 , then having the carry added and so on

so in case 2 , we make sure that all 1s in x are 0s in y , till we reach the first 0 in x , which is a 1 in y , then all symbols are the same

other cases :

when we reach the state same we expect both binary strings to be the same from this point on , but x or y may have different number of leading 0s

the leading 0s are found at beginning of y , thus at end of y^r , so if we reach the accept state , meaning y = x+1 , we allow reading as much 0s as we want since we know these are leading 0s that do not change the number

if x is the one with more leading 0s , then we guess non-deterministically that input has ended , and what remains on stack are all leading 0s , we head to the state x 0s where we pop all leading 0s then accept , of course in the process if we are face with a 1 , this means these 0s are not leading 0s and we reject

we mentioned how if y ends with a 1 , we need to check for the first 0 in x to change to 1 in y , but what if x has only 1s ? , ex x = 1 , y = 10 , we check that 1 has turned to 0 , then if we find no 0s , we will find the # , the # will tell us that the string ended , and thus when x = 1 , the stack is #1 but we treat the # as a leading 0 , then we push it back for the final check for empty string , so the original rule is 1,0,ε , the rule we add is 1,#,# , we pop the # instead of the 0 ,fair enough since we know this is the end of the string anyway so we can say that #1 is same as #01 , then we push the # again for the final test of emptiness of stack

Now here is the PDA :

Answer 2

Actually, $y^r$ is not necessarily equal to $x^r+1$. Think about $10 = 1 + 1$ but $01 \neq 1 + 1$ as a counterexample.

The reverse of $y$ really gives a helpful hand.

Aside: $x\$y$ where $x$ and $y$ has the same meaning as above is not a CFL.

Hint: apply pumping lemma to this string: $\underbrace{11\cdots 1}_p0\underbrace{11\cdots 1}_p\$\underbrace{11\cdots1}_{p+1}\underbrace{00\cdots0}_p$.

In this circumstance, it is a good manner to remember whether the PDA has read through the string of $'1'$ in the front when disposing of $y^r$, which is represented by the self-looping edge of the node $D$. For simplicity, we confine $x$ to a positive integer and require that $0$ should not be the prefix either in $x$ or $y$.

The reason why there are two ways out of $D$ is that if $x$ is a string full of $1$, then the length of $y$ is one more than $x$. In other cases, $x$ and $y$ should always be at the same length.