Построить перечислитель (принтер) для {0 ^ (3 ^ n) | n> = 0} не более 10 состояний, включая печать и остановку, ограниченный алфавит?

Question

У меня есть задача создать перечислитель (машина Тьюринга, который также печатает на ленту вывода и выводит его, перейдя в состояние print) для языка {0 ^ (3 ^ n) | n >= 0}, где:

1) Количество состояний должно быть не более 10 (, включая print и halt состояний, они входят в 10 состояний)

2) Gamma, алфавит принтера - {0, x, space} и , ничего больше .

3) Выходной алфавит ленты {0}.

Я много раз пытался построить его не более чем с 10 состояниями, но мне удалось использовать 11, а не 10. Моя идея состояла в том, чтобы стереть каждое 0 с пробелом, а затем выполнить итерацию после определенного разделителя, скажем X, и напишите 3 0s для каждого удаленного 0 перед разделителем. Например space|x|space,space,space|x|000000000|x|. "|" только для того, чтобы подчеркнуть разделитель для этого вопроса, пробелы являются предыдущими 0's перезаписанными - после перезаписи каждого 0 с space я итерирую за X и добавляю 3 0s в конце.

Каждый раз, когда я терпел неудачу, мне не хватало еще одного состояния. У меня закончились идеи ... помогите?

Спасибо

Answer 1

Есть много машин, которые могут это сделать. Вот пример одного. У него меньше состояний, чем требуется.

Основная идея такова:

1. начните с печати 0^(3^0) = 0^1 = 0 на ленте.
2. сразу после этого введите print, поскольку 0 - это строка, которую мы должны перечислить.
3. после печати преобразуйте все 0 на ленте в пробелы, читая слева направо
4. после преобразования всех 0 в пробелы, преобразуйте самое правое пространство в 0, затем добавьте два 0 к концу ленты
5. продолжайте шаг 4, пока все пробелы не будут стерты
6. содержимое ленты - это новая строка для перечисления, так как мы взяли предыдущую строку вида 0^(3^n) и утроили каждое вхождение 0, получив строку 0^(3^(n+1)).

Состояния выглядят примерно так:

 Q     T    Q'    T'    Mv
--    --    --    --    --
q0     x    pr     0    same
print  0    q1    sp    same
q1     0    q1    sp    right
q1     x    q2     x    left
q2     x    pr     x    right
q2    sp    q3     0    right
q2     0    q2     0    left
q2     x    pr     x    right
q3     0    q3     0    right
q3     x    q4     0    right
q4     x    q2     0    left

И вот как это выглядит при печати 0^(3^2) = 0^9:

xxxxxxxxxxxxxxxxxxxx
 ^ q0
x0xxxxxxxxxxxxxxxxxx
 ^ pr
x xxxxxxxxxxxxxxxxxx
 ^ q1
x xxxxxxxxxxxxxxxxxx
  ^ q1
x xxxxxxxxxxxxxxxxxx
 ^ q2
x0xxxxxxxxxxxxxxxxxx
  ^ q3
x00xxxxxxxxxxxxxxxxx
   ^ q4
x000xxxxxxxxxxxxxxxx
   ^ q2
x000xxxxxxxxxxxxxxxx
  ^ q2
x000xxxxxxxxxxxxxxxx
 ^ q2
x000xxxxxxxxxxxxxxxx
^ q2
x000xxxxxxxxxxxxxxxx
 ^ pr
x 00xxxxxxxxxxxxxxxx
  ^ q1
x  0xxxxxxxxxxxxxxxx
   ^ q1
x   xxxxxxxxxxxxxxxx
    ^ q1
x   xxxxxxxxxxxxxxxx
   ^ q2
x  0xxxxxxxxxxxxxxxx
    ^ q3
x  00xxxxxxxxxxxxxxx
     ^ q4
x  000xxxxxxxxxxxxxx
    ^ q2
x  000xxxxxxxxxxxxxx
   ^ q2
x  000xxxxxxxxxxxxxx
  ^ q2
x 0000xxxxxxxxxxxxxx
   ^ q3
x 0000xxxxxxxxxxxxxx
    ^ q3
x 0000xxxxxxxxxxxxxx
     ^ q3
x 0000xxxxxxxxxxxxxx
      ^ q3
x 00000xxxxxxxxxxxxx
       ^ q4
x 000000xxxxxxxxxxxx
      ^ q2
...
x 000000xxxxxxxxxxxx
 ^ q2
x0000000xxxxxxxxxxxx
  ^ q3
...
x0000000xxxxxxxxxxxx
        ^ q3
x00000000xxxxxxxxxxx
         ^ q4
x000000000xxxxxxxxxx
        ^ q2
...
x000000000xxxxxxxxxx
^
x000000000xxxxxxxxxx
 ^ pr
...