Машина Тьюринга, которая находит четную или нечетную длину

У меня есть вопрос, на котором я застрял:

Опишите формально (т. е. с помощью функции перехода) машину Тьюринга, которая решает, имеет ли входное слово a^n четную или нечетную длину.

Кто-нибудь, пожалуйста, сможет просветить меня о том, что меня просят сделать, поскольку я действительно этого не понимаю ?!

Любая помощь будет высоко оценена, спасибо.


transition turing-machines
person hunterge    schedule 03.12.2013    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Не уверен, что вы все еще ищете решение или нет, но я нашел решение, которое решает его за линейное время. Вот функции перехода, которые будут давать 1 на выходной ленте, если она четная, и 0 в противном случае.

(q_start start blank) --> (R S 1 q_test)
(q_test x 1 ) --> (R S 0 q_test)
(q_test x 0 ) --> (R S 1 q_test)
(q_test blank x) --> (S S x q_halt)

x представляет собой букву данного алфавита.

Я попеременно пишу 1 и 0, пока мы не достигнем конца строки {0,1}*. Как только мы наткнулись на пробел, мы просто возвращаемся, и значение на выходной ленте является нашим ответом.

person Dylan    schedule 29.01.2015

arrow_upward
1
arrow_downward

Вам нужно спроектировать машину Тьюринга, которая получает на вход a^n (a, aa, aaa, aaaa, aaaaa, aaaaaa и т. д., любую строку a...a) и решает, является ли длина нечетной или четной. . Вы должны думать об этом как о вопросе, который нужно решить: является ли длина строки нечетной? тогда ответ будет ДА ​​или НЕТ, если это «НЕТ», вы подразумеваете, что длина четная.

Один ответ, который я могу себе представить, я объясню на примере (вы делаете формальный дизайн):

ввод: ааааааа (a^7)

>aaaaaaa_ #you start at the end and move to the left
        ^
>aaaaaaa #head is on an a
       ^
>aaaaaaY #write a yes
       ^
>aaaaaaY #move to the left
      ^
>aaaaaaY #head is on an a so, we write an N, go right, delete Y and move left twice
      ^
>aaaaaNY
      ^
>aaaaaNY
       ^
>aaaaaN_
       ^
>aaaaaN
      ^
>aaaaaN
     ^

Теперь вы повторяете тот же процесс, но с Y (напишите Y, сдвиньте вправо, удалите N, дважды сдвиньте влево). После нескольких шагов у вас будет:

>aN #head on a, last write was N, so we write Y
 ^
>YN #go right
 ^
>YN #delete N
  ^
>Y_ #go left twice
  ^
>Y
 ^
>Y #now, head is on > (the beginning of the input) so we finished
^
>Y #move right twice and stop
 ^
>Y_
  ^

Там вы получили ответ Y на вопрос «является ли длина a^7 НЕЧЕТНОЙ?»

Попробуйте ту же идею с равной длиной, и вы должны получить

>N_
  ^

Это идея, которую я придумал, может быть, вы найдете более простую машину, теперь вам нужно создать диаграмму или таблицы, чтобы определить ее правильно (это был просто пример, а не определение)

person arieljuod    schedule 03.12.2013