Рубрики

Машина Тьюринга в ТОС

Машина Тьюринга была изобретена Аланом Тьюрингом в 1936 году и используется для принятия рекурсивных перечислимых языков (генерируется грамматикой типа 0).

Машина Тьюринга состоит из ленты бесконечной длины, на которой можно выполнять операции чтения и записи. Лента состоит из бесконечных ячеек, в которых каждая ячейка содержит либо входной символ, либо
специальный символ, называемый пустым. Он также состоит из указателя головы, который указывает на ячейку, читаемую в данный момент, и может перемещаться в обоих направлениях. TM выражается в виде 7-кортежа (Q, T, B, ∑, δ, q0, F), где:

  • Q — конечное множество состояний
  • T — ленточный алфавит (символы, которые могут быть написаны на ленте)
  • B — пустой символ (каждая ячейка заполняется B, кроме входного алфавита изначально)
  • — входной алфавит (символы, которые являются частью входного алфавита)
  • δ — функция перехода, которая отображает Q × T → Q × T × {L, R}. В зависимости от текущего состояния и текущего алфавита ленты (на который указывает указатель головки), он переместится в новое состояние, изменит символ ленты (может или не может) и переместит указатель головки влево или вправо.
  • q 0 — начальное состояние
  • F — множество конечных состояний. Если какое-либо состояние F достигается, входная строка принимается.

Построим машину Тьюринга для L = {0n1n | n> = 1}

  • Q = {q0, q1, q2, q3}, где q0 — начальное состояние.
  • T = {0,1, X, Y, B}, где B представляет собой пробел.
  • ∑ = {0,1}
  • F = {q3}

Функция перехода δ приведена в таблице 1 как:

иллюстрация

Давайте посмотрим, как эта машина Тьюринга работает для 0011. Первоначально head указывает на 0, что подчеркнуто, и состояние q0 как:

Ход будет δ (q0, 0) = (q1, X, R). Это означает, что он перейдет в состояние q1, замените 0 на X и голова будет двигаться вправо как:

Ход будет δ (q1, 0) = (q1, 0, R), что означает, что он останется в том же состоянии и без изменения какого-либо символа, он будет двигаться вправо как:

Движение будет δ (q1, 1) = (q2, Y, L), что означает, что он переместится в состояние q2 и из 1 в Y переместится влево как:

Работая над ним таким же образом, машина достигнет состояния q3, и головка укажет на B, как показано:

Используя ход δ (q3, B) = остановка, он остановится и будет принят.

Замечания:

  • В недетерминированной машине Тьюринга может быть более одного возможного перемещения для данного состояния и символа ленты, но недетерминированная ТМ не добавляет никакой мощности.
  • Каждая недетерминированная ТМ может быть преобразована в детерминированную ТМ.
  • В многоленточной машине Тьюринга может быть несколько лент и соответствующие указатели головок, но это не добавляет мощности к машине Тьюринга.
  • Каждую многолентную ТМ можно преобразовать в одну ленточную ТМ.

Вопрос: Одна машина ленты Тьюринга M имеет два состояния q0 и q1, из которых q0 является начальным состоянием. Алфавит ленты M равен {0, 1, B}, а его входной алфавит — {0, 1}. Символ B — это пустой символ, используемый для обозначения конца входной строки. Функция перехода M описана в следующей таблице.

Таблица интерпретируется как показано ниже. Запись (q1, 1, R) в строке q0 и столбце 1 означает, что если M находится в состоянии q0 и читает 1 в текущем квадрате ленты, то он записывает 1 в тот же квадрат ленты, перемещает головку ленты на одну позицию в право и переходы в состояние q1. Какое из следующих утверждений верно для M?

  1. M не останавливается ни на одной строке в (0 + 1) +
  2. M не останавливается ни на одной строке в (00 + 1) *
  3. M останавливается на всей строке, заканчивающейся на 0
  4. M останавливается на всей строке, заканчивающейся на 1

Решение: Посмотрим, остановится ли машина на строке '1'. Первоначально состояние будет q0, голова будет указывать на 1 как:

Используя δ (q0, 1) = (q1, 1, R), он переместится в состояние q1, а голова переместится вправо как:

Используя δ (q1, B) = (q0, B, L), он переместится в состояние q0, а голова переместится влево как:

Он будет работать одинаково снова и снова и не останавливаться.

Опция D говорит, что M останавливается на всей строке, заканчивающейся на 1, но не останавливается на 1. Таким образом, опция D неверна.

Посмотрим, остановится ли машина на строке '0'. Первоначально состояние будет q0, голова будет указывать на 1 как:

Используя δ (q0, 0) = (q1, 1, R), он переместится в состояние q1, а голова переместится вправо как:

Используя δ (q1, B) = (q0, B, L), он переместится в состояние q0, а голова переместится влево как:

Он будет работать одинаково снова и снова и не останавливаться.

Опция C говорит, что M останавливается на всей строке, заканчивающейся на 0, но не останавливается на 0. Таким образом, опция C неверна.

Вариант B говорит, что TM не останавливается ни для одной строки (00 + 1) *. Но NULL-строка является частью (00 + 1) *, и TM остановится для NULL-строки. Для пустой строки лента будет

Используя δ (q0, B) = останов, TM остановится. Поскольку TM останавливается для NULL, эта опция также неверна.
Таким образом, вариант (А) является правильным.

Эта статья предоставлена Sonal Tuteja . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Машина Тьюринга в ТОС

0.00 (0%) 0 votes