Вот условие:

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

Сложность в присутствии ε, ведь на ленте может присутствовать этот символ и тогда, как я думаю, нужно вводить для него отдельные состояния. Что на порядок усложняет задачу

задан 13 Янв '15 17:07

10|600 символов нужно символов осталось
0

Нужно переработать имеющуюся на ленте запись в запись вида $%0...0\varepsilon...\varepsilon1...1$%. Для этого надо устранить все подслова трёх видов: $%\varepsilon0$%, $%10$% и $%1\varepsilon$%, переставляя в них буквы местами. После конечного числа таких действий получится та запись, которая нам нужна.

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

Тот символ, который только что был прочитан машиной, будем запоминать в виде состояния: $%q_0$% оставляем для прочтённого нуля, $%q_1$% для $%1$% и $%q_2$% для $%\varepsilon$%. Если в состоянии $%q_1$% мы читаем на ленте $%0$%, то это означает, что возникло подслово $%10$%, и в нём надо переставить буквы. Переходим в состояние $%q_3$%, печатаем $%1$% на месте нуля, сдвигаемся влево. Там мы видим символ $%1$%, и в программу добавляем команду, которая в этой ситуации предписывает написать $%0$%, перейти в состояние $%q_0$% и сдвинуться влево. Далее машина выполняет действия в цикле; если она видит пустой символ, то остаётся в состоянии $%q_0$% и сдвигает головку вправо.

Аналогично поступаем с другими "запрещёнными" подсловами. А именно, если в состоянии $%q_1$% мы видим символ $%\varepsilon$%, то пишем на его месте $%1$%, сдвигаемся влево, переходя в $%q_4$%. В этом состоянии мы на месте $%1$% пишем $%\varepsilon$%, переходим в $%q_0$% и сдвигаем головку влево.

То же самое происходит, когда в состоянии $%q_2$% мы видим $%0$%, и здесь мы для аналогичной цели используем состояние $%q_5$%.

ссылка

отвечен 14 Янв '15 6:47

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

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

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

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

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

отмечен:

×941

задан
13 Янв '15 17:07

показан
578 раз

обновлен
14 Янв '15 13:38

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

по почте:

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

по RSS:

Ответы

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

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