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

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

Решение задач по машинам Тьюринга из сборника turing-practice.pdf.

Упр. 4 | Восстановление языка по машине Тьюринга

Задание

Для следующей машины Тьюринга привести распознаваемый ею язык.

08-01.png

Решение

Альтернативный способ задания МТ — автомат. Здесь узлы графа — состояния, а на рёбрах правила перехода по определённому символу $$(\sqcup \equiv \lambda) $$. Например, из состояния $$q_0$$ по $$1$$ мы оставляем её и переходим вправо ($$R$$), оставаясь в состоянии $$q_0$$; а по $$0$$ также оставляем значение, передвигаемся вправо, но переходим уже в состояние $$q_1$$.

Данная задача решается просто аналитически. Заметим, что в данной МТ ни один символ не заменяется. Конечная вершина — $$q_3$$, т. е. только слова, завершившиеся в $$q_3$$, принадлежат искомому языку. На самом деле данный автомат эквивалентен некоторому обычному конечному автомату.

Построим все возможные пути из $$q_0$$ в $$q_3$$.

$$ \begin{array}{ll} {q_0q_1q_2q_3} & {1^* 0^+ 1^+} \\ {q_0q_1q_2q_4q_3} & {1^* 0^+ 1^+0^+} \\ {q_0q_1q_2q_4q_5q_1q_2q_3} & {1^* 0^+ 1^+ 0^+ 1^+ 0^+ 1^+} \\ {q_0q_1q_2q_4q_5q_1q_2q_4q_3} & {1^* 0^+ 1^+ 0^+ 1^+ 0^+ 1^+ 0^+} \\ . . . & \\ \end{array} $$

Заметим, что следующие переходы состояний $$q_1 \to q_1 \colon q_1 q_2 q_4 q_5 q_1$$ по выражению $$1^+ 0^+ 1^+ 0^+ $$ есть петля. Дать окончательный ответ поможет построение следующего НКА:

08-02.png

Таким образом, регулярное выражение $$1^*0^+\left((1^+0^+)^2\right)^*1^+0^*$$ описывает искомый язык.

Упр. 7 | Грамматика

Задание

Рассмотреть следующую регулярную грамматику: $$G=\langle \{a,b\}, \{A\}, A,\{A\to aA, A\to b\}\rangle $$

Используя её, построить машину Тьюринга, разрешающую язык $$L(G)$$.

Решение

Регулярное выражение $$a^*b$$ описывает язык $$L(G)$$. Машина Тьюринга должна пробежать по всем $$a$$, встретив $$b$$ перейдёт в другое состояние, в котором в случае $$\lambda$$ после $$b$$ примет слово, иначе отклонит его.

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

$$ \begin{array}{r|ccc} \delta\ & a & b & \lambda \\ \hline \to q_0 & a,R,q_0 & b,R,q_1 & \_,\_,q_{rej} \\ q_1 & a,\_,q_{rej} & b,\_,q_{rej} & \_,\_,q_{acc} \\ q_{acc}^* & & & \\ q_{rej}^* & & & \\ \end{array} $$

Здесь «$$\_$$» означает, что можно подставить любое допустимое значение (т. е. неважно дальнейшее направление движение/записываемый символ)

Упр. 9 | $${1^n \to 1^{2^n}}$$

Задание

Опишите машину Тьюринга, вычисляющую функцию $${1^n \to 1^{2^n}}$$.

Идея решения

Приведём несколько тестовых примеров: $$\lambda \equiv 1^0 \to 1^{2^0} = 1^1 \equiv 1$$, $$1 \equiv 1^1 \to 1^{2^1} = 1^2 \equiv 11$$ и $$11 \equiv 1^2 \to 1^{2^2} = 1^4 \equiv 1111$$.

Пробегаем по входному слову до конца, устанавливаем символ $$\#$$ для разделения исходных данных и промежуточного результата (инициализируем его $$1$$). Далее удаляем единицу из исходных данных и удваиваем промежуточный результат за решёткой. Дублирование производится схожим образом: устанавливаем решётку за последним промежуточным результатом, удаляя единицы из промежуточного результата, ставим их за поставленной решёткой; затем, когда все единицы между двумя решётками удалены, удаляем крайнюю правую единицу и заменяем все $$\lambda$$ между решётками и правую решётку, поставленную для процесса дублирования, на единицы.

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

$$ \begin{array}{r|ccc} \delta\ & 1 & \# & \lambda \\ \hline \to q_0 & 1,R,q_0 & — & \#,R,q_1 \\ q_1 & — & — & 1,L,q_2 \\ \hline & \text{алгоритм} & \text{возведения} & \text{в степень} \\ \hline q_2 & 1,L,q_2 & \#,L,q_2 & \lambda,R,q_3 \\ q_3 & \lambda,R,q_4 & \lambda,R,q^* & — \\ q_4 & 1,R,q_4 & \#,R,q_5 & — \\ \hline & \text{начало} & \text{процесса} & \text{дублирования} \\ \hline q_5 & 1,R,q_5 & — & \#,L,q_6 \\ q_6 & 1,L,q_6 & \#,R,q_7 & \lambda,R,q_7 \\ q_7 & \lambda,R,q_8 & 1,R,q_{11} & — \\ q_8 & 1,R,q_8 & \#,R,q_9 & — \\ q_9 & 1,R,q_9 & — & 1,L,q_{10} \\ q_{10} & 1,L,q_{10} & \#,L,q_6 & — \\ \hline & \text{завершение} & \text{процесса} & \text{дублирования} \\ \hline q_{11} & 1,R,q_{11} & — & \lambda,L,q_{12} \\ q_{12} & \lambda,L,q_{13} & — & — \\ q_{13} & 1,L,q_{13} & \#,L,q_2 & 1,L,q_{13} \\ q^* & & & \end{array} $$