Построить КПК, который удовлетворяет {ш |w∈ {0,1, #} ∗, w = b (n) R # b (n + 1), n≥1, b (x) преобразует x в двоичный файл без начального 0}

Question

Создание КПК для языка {w |w∈ {0,1, #} ∗, w = b (n) R # b (n + 1), n≥1, b (x) преобразует x в двоичный файл без начального 0}

b (n) R означает, что двоичная строка перевернута.

Я пытался создать CFG, который мог бы описать этот язык, а затем перейти на КПК, но я не знаю, с чего начать.Я думал, что есть некоторая связь между числом 0 и 1, которые соответствуют двоичному числу b (n + 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, мы знаем, что будет перенос, связанный с +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