ТМВ-2020-Семинар-03.04.2020

Материал из Кафедра Прикладной Математики
Перейти к навигации Перейти к поиску

Машина Тьюринга

Машина Тьюринга представляет собой машину с бесконечной лентой, обладающую считывающей/записывающей головкой, которая может двигаться влево, вправо либо оставаться на месте. Так же, как и ранее имеем алфавит, состояния, строим таблицу переходов и т. д. Машина Тьюринга, находясь в некотором состоянии, считывает символ алфавита и, считав его, может совершить переход в новое состояние и осуществить движение. Подробнее о машине Тьюринга читай в лекции 6.

Решение задач

Задача 1. Распознавание слов $${0^n1^n}$$

Формулировка задачи

Построить машину Тьюринга, распознающую следующий язык $$L=\{0^n1^n\}$$.

Идея решения

Рис. 1 — Процесс распознавания слова $$000111$$ машиной Тьюринга

Приведём примеры слов, удовлетворяющих и не удовлетворяющих языку. Например, $$000111, \lambda \in L, \text{ a } 0, 1, 011 \not\in L$$. Строя КС-грамматику для данного языка, мы исходили из рекурсии. На самом деле, в МТ выгоднее идти в обратном направлении, исходя из имеющихся данных: попробовать разложить их обратно или как-то уничтожить и т. п. В нашем случае, например, уничтожив слово по определённым правилам, корректной будет ситуация, при которой останется только $$\lambda$$ и чётную длину.

Таким образом, наша идея следующая: каретка, удаляя первый символ (если он $$0$$) движется далее вправо до конца слова, удаляет последний символ (если он $$1$$) и движется обратно влево и т. д. Процесс для слова $$000111$$ изображён на рисунке 1.

Таблица переходов

$$ \begin{array}{r|ccc} \delta\ & 0 & 1 & \lambda \\ \hline \to q_0 & \lambda, q_1, R & 1, q_{rej}, \sqcup & \lambda, q_{acc}, \sqcup \\ q_1 & 0, q_1, R & 1, q_1, R & \lambda, q_2, L \\ q_2 & 0, q_{rej},\sqcup & \lambda, q_3, L & \lambda, q_{acc}, \sqcup \\ q_3 & 0, q_3, L & 1, q_3, L & \lambda, q_0, R \\ \end{array} $$

Пояснения к обозначениям

  • $$q_i$$ — промежуточные состояния МТ ($$q_0$$ — начальное);
  • $$q_{acc}, q_{rej}$$ — допускающее и отклоняющее состояния соответственно;
  • $$L, R, \sqcup$$ — направление движения каретки: влево, вправо и на месте соответственно.

Задача 2. Двойное слово

Формулировка задачи

Построить машину Тьюринга, распознающую следующий язык $$L=\{\omega\omega \mid {\omega\in \{0, 1\}^*}\}$$.

Идея решения

Рис. 2 — Процесс распознавания слова $$0101$$ машиной Тьюринга

Как и в задаче 1 определим подходящие и неподходящие слова. Например, $$\lambda, 00, 11, 0101$$ — допускаются, а $$0, 0110, 10$$ — нет. Очевидно, что допустимое слово имеет чётную длину, т. е. слова, имеющие нечётную длину, должны сразу отсекаться. Однако необходимо как-то разделить слово на две половины. Для этого промаркируем наше слово по следующим правилам:

  • $$0\to0'$$ и $$1\to1'$$ для крайнего левого непромаркированного символа (затем ищем крайний правый непромаркированный символ);
  • $$0\to0''$$ и $$1\to1''$$ для крайнего правого непромаркированного символа (затем ищем крайний левый непромаркированный символ).

После преобразований возвращаемся в начало слова и начинаем сопоставлять символы в половинках слова. Например, первый символ $$0'$$, тогда ставим снова на это $$0$$ и ищем первый символ с двумя штрихами и, если он $$0''$$, то так же заменяем его на $$0$$ и аналогично продолжаем сопоставление, иначе делаем вывод, что слово не принадлежит языку (переходим в состояние $$q_{rej}$$.Процесс для слова $$0101$$ изображён на рис. 2.

Таблица переходов

$$ \begin{array}{r|ccccccc} \delta\ & 0 & 1 & \lambda & 0' & 1' & 0'' & 1'' \\ \hline \to q_0 & 0',q_1,R & 1',q_1,R & \lambda, q_{acc}, \sqcup & — & — & 0'',q_{0'}, L & 1'',q_{0'}, L \\ q_1 & 0, q_1,R & 1, q_1,R & \lambda, q_2, L & — & — & 0'', q_2, L & 1'', q_2, L \\ q_2 & 0'',q_3,L & 1'',q_3, L & — & 0',q_{rej}, L & 1',q_{rej}, L & — & — \\ q_3 & 0, q_3, L & 1, q_3, L & — & 0',q_0,R & 1',q_0,R & — & — \\ \hline q_{0'} & 0,q_4,R & 1,q_4,R & \lambda,q_4,R & 0',q_{0'},L & 1',q_{0'},L & — & — \\ q_4 & — & — & — & 0, q_5,R & 1, q_6,R & — & — \\ q_5 & 0, q_5,R & 1,q_5,R & — & 0',q_5,R & 1',q_5,R & 0,q_7,L & 1'',q_{rej},\sqcup \\ q_6 & 0,q_6,R & 1, q_6,R & — & 0', q_6,R & 1',q_6,R & 0'',q_{rej},\sqcup & 1,q_7,\sqcup \\ q_7 & 0,q_7,L & 1,q_7,L & \lambda,q_{acc},\sqcup & 0',q_{0'},L & 1',q_{0'},L & — & — \\ \end{array} $$