Construct a PDA for the language {w | w∈{0,1,#}∗,w=b(n)R#b(n+1),n≥1, b(x) converts x to binary with no leading 0}
b(n)R means the binary string reversed.
I tried making a CFG that can describe this language and then converting to PDA, but I don't really know how to start. I was thinking there is some relationship between the number of 0 and 1s that correspond to the b(n+1) binary number?
Some Examples:
For n=1, the recognized string is "1#10"
For n=2, the recognized string is "01#11"
For n=3, the recognized string is "11#100"
For n=4, the recognized string is "001#101"
If we start with a 1, we know there is going to be carry involved from the +1 on the RHS, so we can record the inverse and stay in a state where we have the carry. Once we lose the carry we can't get it back and can just remember the digits we're seeing. So:
q S s q' S'
q0 Z0 0 q1 1Z0 starts with 0, no carry, just copy
q0 Z0 1 q2 0Z0 starts with 1, some carry, copy backwards
q1 x 0 q1 0x no more carry, just copy input
q1 x 1 q1 1x to stack so we can read it off backwards
q1 x # q3 x
q2 x 0 q1 1x still have carry, keep carrying as long
q2 x 1 q2 0x as we keep seeing 1
q2 x # q4 # (go write an extra 1 of we carried all the way)
q3 0x 0 q3 x read back the stack contents, backwards
q3 1x 1 q3 x
q3 Z0 - q5 Z0
q4 x 1 q3 x if the LHS is 1^n, write the extra 1 on RHS
q5 accepting state reachable on empty stack