Унарные языки распознаются двусторонними детерминированными счетными автоматами

17

2dca (двусторонние детерминированные автоматы с одним счетчиком) (Petersen, 1994) могут распознавать следующий унарный язык:

POWER={02nn0}.

Есть ли другой нетривиальный унарный язык, распознаваемый 2dca?

Заметьте, что до сих пор неизвестно, могут ли 2dca распознать ?SQUARE={0n2n0}


ОПРЕДЕЛЕНИЕ: 2dca - это двусторонний детерминированный конечный автомат со счетчиком. 2dca может проверить, является ли значение счетчика нулевым или нет, и увеличивать или уменьшать значение счетчика на 1 на каждом шаге.

Абузер Якарылмаз
источник
3
Не могли бы вы добавить ссылку на определение 2DCA?
Суреш Венкат
3
@SureshVenkat: я добавил ссылку, а также определение.
Абузер Якарылмаз
1
@AbuzerYakaryilmaz: для каждого фиксированного он может распознать { 0 k n : n 0 }k{0kn:n0}
Марцио Де Биаси
@MarzioDeBiasi: Алгоритм для может быть легко обобщен до P O W E R k = { 0 k nn 0 } , где k 3 . Поэтому эти языки довольно тривиальны для меня. POWERPOWERk={0knn0}k3
Абузер Якарылмаз
1
Хм, на самом деле, я думаю, что таким образом, я просто заканчиваю тем же наблюдением, которое уже сделал Марцио, так что ничего нового в том, что я сказал. Мне все еще интересно, нужно ли нам читать конечный маркер больше, чем ограниченное число раз.
Домоторп

Ответы:

6

Это всего лишь идея, которая пришла мне в голову при чтении Марвина Л. Минского «Рекурсивная неразрешимость проблемы метки Поста и других тем в теории машин Тьюринга»; в частности, знаменитая теорема Ia:

Теорема Ia: Мы можем представить любую частично рекурсивную функцию программой, работающей с двумя целыми числами S 1 и S 2, используя инструкции I j в следующих формах: (i) ДОБАВИТЬ 1 в S j и перейти к I j 1 ( ii) ПОДРЯД 1 из S j , если S j0 и перейти к I j 1 , иначе перейти к I j 2 То есть мы можем построить такую ​​программу, которая начинается с S 1f(n)S1S2Ij
SjIj1
SjSj0Ij1Ij2
и S 2 = 0 и в конечном итоге останавливается с S 1 = 2 f ( n ) и S 2 = 0S1=2nS2=0S1=2f(n)S2=0

Если у вас есть двусторонний DFA с одним счетчиком на (полу) бесконечной ленте, где ввод задается в унарном виде: тогда DFA может:$12n000...

  1. прочитать унарный ввод (и сохранить его в счетчике);
  2. работать на части ленты и использовать расстояние от 1 с в качестве второго счетчика.01

таким образом, он может моделировать полный счетчик Тьюринга.

Теперь, если у вас есть рекурсивная функция которая выполняется за время T ( n ) на стандартной машине Тьюринга, двусторонний DFA с одним счетчиком, который запускается на конечной ленте $ 1 m $f(n)T(n) $1m$(где и T ( n ) T ( n ) ) могут:m=2n3T(n)T(n)T(n)

  1. прочитать унарный ввод (и сохранить его в счетчике);
  2. возврат к крайнему левому символу;
  3. делим счетчик на 3 до тех пор, пока счетчик не будет содержать таким образом: идите вправо, зацикливаясь на состояния q z 0 , q z 1 , q z 2 и вычитая 1; если счетчик достигает 0 в состоянии q z 0, перейдите к крайнему левому символу, добавив +1 и продолжив цикл деления, в противном случае добавьте 1 (если в состоянии q z 1 ) или 2 (если в состоянии q z 2 ) и перейдите к крайнему левому символу, добавив + 3 (т.е. восстановить предыдущее значение счетчика, не делимого на 3) и перейти к шагу 4 .;2nqz0,qz1,qz2qz0qz1qz2
  4. в этот момент счетчик содержит ;2n
  5. вычислите используя пространство T ( n ), доступное справа в качестве второго счетчика (значение второго счетчика - это расстояние от крайнего левого символа $ ).2f(n)T(n)$

Таким образом, с помощью специальной входной кодировки, описанной выше, которая дает достаточно места на конечной ленте, двусторонний DFA с одним счетчиком и унарным алфавитом может вычислять каждую рекурсивную функцию.

Если подход правильный, было бы интересно подумать о том, как выбрать или когда достаточно выбрать большое нечетное k 2 и кодировать входные данные как 1 m , m = 2 н к нT(n)T(n)k21mm=2nkn

Марцио де Биаси
источник
-1

Под нетривиальным я предполагаю, что вы имеете в виду язык L, который не может быть принят 1dca. Вот вроде бы такой язык:

ЦЕНТР = {ш | w больше {0,1} * и w = x1y для некоторого x, y такого, что | x | = | y |}

Этот язык не может быть принят 1dca, но МОЖЕТ быть принят 1nca. Это может быть принято 2dca. Детали оставлены в качестве упражнения.

user14004
источник
2
ОП запрашивает унарные языки (входные данные задаются как )$1n$
Марцио Де Биаси