Нарисуйте схему две ленты Non детерминированной машины Тьюринга M, который принимает решения, языкупостроение не детерминированная машина Тьюринга
L = {w∈Σ * | ш = и у у ∈Σ *}
, если я мог бы получить помощь объяснить шаги, как построить NDTM (лингвистический), я полагаю, что я мог бы нарисовать диаграмму, но я не смог выйти с ответом ..
спасибо
по u*u*u (рассматриваются в истории редактирования), я полагаю, что вы собираетесь это язык всех слов вида и^3 (и повторяется три раза), где и любая строка в алфавите ,
Наш NDTM должен принимать строки на языке, по крайней мере, одним способом, и он никогда не должен принимать ничего, кроме языка. В частности, ключ заключается в том, что NDTM может отклонять строки в языке, если какой-то путь через NDTM принимает каждую строку на этом языке.
Учитывая, что наш первый шаг может быть догадаться о длине u. NDTM может отмечать три символа ленты (например, путем написания версий подчеркнутых символов) путем недетерминированного перехода из состояния q0 в q1, затем q2 в произвольных точках при правильном сканировании. Затем мы можем сбросить ленточную головку и использовать детерминированную ТМ для ответа на вопрос: раскол, который мы догадались на первом шаге, приводит к строке формы u^3?
Это детерминированное, поскольку мы знаем разграничение частей. Мы можем проверить первые две части (скажем, отскакивая назад вперед и маркируя символы, которые мы уже обработали), а затем две две части (используя ту же технику, но применительно ко 2-й и 3-й частям).
Мы привели проблему к проверке того, имеет ли строка форму w|w, где мы знаем раздвоение. Эту детерминированную ТМ легче придумать. Когда мы помещаем его после NDTM, который догадывается о том, как разделить начальный ввод, мы получаем NDTM, который может (и точно догадываться) принимать любую строку формы u^3, но не может принять ничего другого. Это то, за чем мы были, и мы закончили.