Построение недетерминированной машины Тьюринга

Question

Нарисуйте схему двухдетерминированной недетерминированной машины Тьюринга M, которая решает язык

L = {w∈Σ * | w = uu u ∈Σ *}

Если бы я мог получить помощь в объяснении шагов, как построить NDTM (лингвистически), я бы мог нарисовать диаграмму, но я не смог бы дать ответ..

благодарю вас

Answer 1

От u*u*u (рассматривается в истории редактирования), я предполагаю, что вы намерены использовать язык всех слов вида u^3 (u повторяется три раза), где u - любая строка над алфавитом.

Наш NDTM должен принимать строки на языке по крайней мере одним способом, и он никогда не должен принимать ничего, кроме языка. В частности, ключ заключается в том, что NDTM может отклонять строки в языке, если какой-то путь через NDTM принимает каждую строку в языке.

Учитывая это, наш первый шаг можно сделать предположение о длине u, NDTM может маркировать три символа ленты (скажем, путем записи версий символов, которые подчеркнуты) путем недетерминированного перехода из состояния q0 в q1 затем q2 в произвольных точках при сканировании вправо. Затем мы можем сбросить головку ленты и использовать детерминированную ТМ, чтобы ответить на вопрос: привело ли разбиение, которое мы догадались на первом шаге, к строке вида u^3?

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

Мы сократили проблему до проверки того, имеет ли строка вид w|w где мы знаем раскол. Эту детерминированную ТМ легче придумать. Когда мы помещаем его после NDTM, который догадывается о том, как разделить начальный ввод, мы получаем NDTM, который может (и только для одного предположения делает) принять любую строку вида u^3, но не может принять ничего другого. Это то, что мы были после, и мы сделали.