Здравствуйте! Нужна помощь с задачкой:

Опишите машину Тьюринга, которая проверяет, что её вход имеет вид 0m1n02m , причём n > 0. Поясните, почему эта программа работает правильно. (При написании программы можно предполагать, что машина имеет 2 завершающих состояния: принимающее qa и отвергающее qr. Если машина приходит в одно из этих состояний, то вычисление останавливается)

Спасибо большое!

задан 16 Июн '17 17:51

изменен 18 Июн '17 22:07

Хотелось бы уточнить несколько моментов по условию. Допустим, нам дано слово 10101. В зависимости от того, какое из двух вхождений мы вычеркнем, может получиться разный результат: 01 или 10. Считается ли это существенным? То есть имеется ли дополнительное требование о вычёркивании непременно слева направо, как-то ещё, или вычёркивать можно как угодно -- лишь бы вхождений 101 больше не осталось? Второй момент: как машина распознаёт конец записи? Есть ли специальный маркер конца, или там стоит пустой символ, который не отождествлён с символом 0?

(16 Июн '17 18:39) falcao

@falcao Вычеркиваем, лишь бы 101 не встретилось, т.е. 10101 полностью. В конце стоит специальный символ, означающий конец записи.

(16 Июн '17 19:05) AlwaysNeedHelp

@AlwaysNeedHelp: пока что не до конца понятны правила. Вот, допустим, у меня есть слово 101011. Имею ли я право вычеркнуть 101 в начале, получая слово 011 без запрещённых вхождений? Или я обязан вычёркивать максимальные по длине вхождения слов вида 101...01, приходя в данном случае к слову 1? А есть ещё вариант, когда я решаю вычеркнуть сначала второе вхождение 101, приходя к 101, и вычёркивая его на следующем шаге, приходя к пустому слову? Все эти вещи должны быть чётко оговорены в условии. Тем более, что здесь f есть функция от x, и тогда итог считается однозначным.

(16 Июн '17 19:19) falcao

@falcao Соглашусь, условие немножко непонятное. И все-таки, правильно в вашем случае делать так: вычеркиваем любые сочетания 101 и получаем в вашем случае итоговый ответ 1.

(16 Июн '17 19:34) AlwaysNeedHelp

@AlwaysNeedHelp: если получается первый вариант, то вычёркиваем мы не любые, а максимальные по длине подслова вида 101...01, идя слева направо. В такой формулировке получается однозначность. Кроме того, можно показать, что при этом не потребуется второй проход. Тогда программу машины я могу схематично описать.

(16 Июн '17 19:47) falcao

@falcao Можете пожалуйста дать схематичное описание этой машины?

(17 Июн '17 21:28) AlwaysNeedHelp

@AlwaysNeedHelp: постараюсь вскоре сделать. Вчера просто малость устал, и уже поленился излагать.

(17 Июн '17 22:47) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
0

Попробую кратко описать схему действий машины. Для удобства заменим обозначения: пусть речь идёт о словах вида bab..ab, максимальные вхождения которых мы удаляем, идя слева направо. При этом новых подслов такого вида появляться не будет, что было отмечено в комментариях. Через 0 будем обозначать пустой символ (поскольку пробел неудобно изображать на письме).

Пусть машина начинает читать слово с крайнего левого символа в состоянии q0. При виде a она остаётся в этом состоянии и сдвигает головку вправо. При виде b она меняет этот символ на пустой и переходит в q1, сдвигаясь вправо. Далее в q1 она может увидеть символ b, или пустой символ, который означает, что b был стёрт зря. Делаем возврат назад, восстанавливаем стёртый символ b, а потом движемся вправо и переходим в q0 перед чтением того символа b, на котором мы "споткнулись", или до пустого символа. Последнее будет означать конец работы. Понятно, что дальше происходит всё то же самое.

Пусть теперь в q1 мы увидели a. Тогда заменяем его на 0, движемся вправо, переходя в q2. Допустим, что мы не увидели b, то есть увидели a или пустой символ. Переходя в новые состояния q3, q4, делаем "откат" влево, и восстанавливаем стёртые символы. Потом идём вправо, и всё повторяется в цикле.

Если же в q2 мы увидели b, то начало bab подлежало удалению. Далее переходим поочерёдно в состояния q5, q6, если видим далее abab... , что также стираем. Если увидели не тот символ, то следует возврат влево с восстановлением одного или двух ошибочно стёртых символов. Однако теперь, когда часть слова стёрта, нужно не продолжать работу в цикле, а сначала "подтащить" оставшуюся справа часть слова, сдвигая её влево. То есть, когда процесс стираний в слове bab...ab закончился, мы идём вправо, находим символ, заменяем его на пустой, попутно заглядывая влево, чтобы узнать, не был ли они последним. Этот факт мы запоминаем при помощи особых состояний, равно как и значение стёртого символа. Далее идём влево, печатаем символ на нужном месте, а потом, если справа что-то осталось, продолжаем циклическую процедуру.

После того, как слово стало "сплошным", начинаем его преобразовывать с нужного места (которое мы знаем) в состоянии q0. Если в нём мы видим пустой символ, то останавливаемся.

Детальное описание в виде готовой программы представляется слишком трудоёмким, поэтому такого рода "блюдо" нет желания "готовить" :)

ссылка

отвечен 18 Июн '17 2:29

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

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

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

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

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

отмечен:

×888
×53
×29

задан
16 Июн '17 17:51

показан
588 раз

обновлен
18 Июн '17 22:07

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

по почте:

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

по RSS:

Ответы

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

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