构造一个满足{w _w R#b{0，1，#}∗，n(N)R#b(n+1)，n≥1，b(x)将x转换为不带前导0}的二进制的PDA。

Question

为语言{w \w_ w∈{0,1，#}∗，w=b(n)R#b(n+1)，n≥1，b(x)构造一个PDA语言，将x转换为没有前导0}的二进制。

b(n)R是指反向的二进制字符串。

我试着做了一个CFG，可以描述这种语言，然后转换到PDA，但我真的不知道如何开始。我在想，与b(n+1)二进制数对应的0和1s的数目之间有某种关系吗？

一些例子：

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"

Answer 1

如果我们从1开始，我们知道RHS上的+1会包含进位，所以我们可以记录逆，并保持在有进位的状态。一旦我们失去了携带，我们就无法拿回它，只记得我们看到的数字。所以：

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