Построить машину Тьюринга, выполняющую операцию конкатенация двух цепочек, заданных во входном алфавите $$A= \{0, 1, *, ε\}$$

задан 4 Июн '15 10:56

изменен 4 Июн '15 21:12

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

Нужно уточнить некоторые мелкие детали. Считается ли, что строки (цепочки), конкатенацию которых надо осуществить, разделены нулём, или специальным пустым символом? Это не слишком принципиально, но уточнить хотелось бы.

(4 Июн '15 12:07) falcao

В описании задания этот момент не указан.

(4 Июн '15 12:16) Greed832
10|600 символов нужно символов осталось
0

Будем считать, что головка находится на крайнем левом символе. В начальном состоянии проходим вправо, оставляя все символы на месте. Когда дойдём до пустого символа, разделяющего строки, переходим в новое состояние $%q$% и сдвигаемся вправо. Если в состоянии $%q$% мы видим $%i$%-й символ входного алфавита, то перебрасываем его влево. А именно, вместо символа пишем пустой, переходим в состояние $%q_i$% (чтобы запомнить, какой это был символ), сдвигаемся влево, пишем $%a_i$% на место пустого символа, а потом сдвигаемся вправо, переходя в состояние $%q$%.

После того, как все символы второй цепочки окажутся переброшены на ячейку влево (всё это происходит в цикле), мы в состоянии $%q$% после сдвига вправо на пустом символе в какой-то момент снова увидим пустой символ. Это значит, что процесс окончен. Далее можно вернуть головку в крайнюю левую позицию, если это необходимо.

ссылка

отвечен 4 Июн '15 23:11

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×94
×78

задан
4 Июн '15 10:56

показан
564 раза

обновлен
5 Июн '15 9:25

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru