构建满足 {w | w∈{0,1,#}∗,w=b(n)R#b(n+1),n≥1, b(x)将x转换为无前导0的二进制}

Question

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表示二进制字符串反转。

我尝试制作一个可以描述这种语言的CFG，然后转换为PDA，但我真的不知道如何开始。我在想b(n+1)二进制数对应的0和1的个数有什么关系？

一些示例：

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

构建满足 {w | w∈{0,1,#}∗,w=b(n)R#b(n+1),n≥1, b(x)将x转换为无前导0的二进制}

Construct a PDA that satisfies {w | w∈{0,1,#}∗,w=b(n)R#b(n+1),n≥1, b(x) converts x to binary with no leading 0}

context-free-grammar

pushdown-automaton