构建满足{W |的PDAw∈{0,1，＃} ∗，w = b(n)r＃b(n 1)，n≥1，b(x)将x转换为二进制，而没

Question

为语言构建PDA {W |w∈{0,1，＃} ∗，w = b(n(r＃b(n 1(，n≥1， b(x(将x转换为二进制，没有领先0}

b(n(r表示二进制字符串反向。

我尝试制作一个可以描述这种语言然后转换为PDA的CFG，但我真的不知道如何开始。我以为与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开头，我们知道将涉及 1的RHS，因此我们可以记录逆并保持处于我们拥有该状态的状态携带。一旦我们丢失了进位，我们就无法将其恢复，只能记住我们看到的数字。所以：

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