ТМ принимает язык, если он входит в конечное состояние для любой входной строки w. Язык рекурсивно перечислим (генерируется грамматикой типа 0), если он принят машиной Тьюринга.
ТМ решает язык, если он его принимает, и переходит в состояние отклонения для любого ввода, не являющегося языком. Язык рекурсивен, если это решено машиной Тьюринга.
Могут быть случаи, когда ТМ не останавливается. Такая ТМ принимает язык, но не решает его.
Проектирование машины Тьюринга
Основные рекомендации по проектированию машины Тьюринга были объяснены ниже с помощью нескольких примеров.
Пример 1
Разработайте TM, чтобы распознавать все строки, состоящие из нечетного числа α.
Решение
Машина Тьюринга М может быть построена следующими движениями:
-
Пусть q 1 будет начальным состоянием.
-
Если М в q 1 ; при сканировании α он переходит в состояние q 2 и записывает B (пусто).
-
Если М в q 2 ; при сканировании α он переходит в состояние q 1 и записывает B (пусто).
-
Из приведенных выше шагов мы можем видеть, что M переходит в состояние q 1, если сканирует четное число α, и входит в состояние q 2, если сканирует нечетное число α. Следовательно, q 2 является единственным принимающим состоянием.
Пусть q 1 будет начальным состоянием.
Если М в q 1 ; при сканировании α он переходит в состояние q 2 и записывает B (пусто).
Если М в q 2 ; при сканировании α он переходит в состояние q 1 и записывает B (пусто).
Из приведенных выше шагов мы можем видеть, что M переходит в состояние q 1, если сканирует четное число α, и входит в состояние q 2, если сканирует нечетное число α. Следовательно, q 2 является единственным принимающим состоянием.
Следовательно,
M = {{q 1 , q 2 }, {1}, {1, B}, δ, q 1 , B, {q 2 }}
где δ определяется как —
| Лента символ алфавита | Современное состояние ‘q 1 ‘ | Современное состояние ‘q 2 ‘ |
|---|---|---|
| α | BRq 2 | BRq 1 |
Пример 2
Разработайте машину Тьюринга, которая читает строку, представляющую двоичное число, и удаляет все первые 0 в строке. Однако, если строка содержит только 0, она сохраняет один 0.
Решение
Предположим, что входная строка заканчивается пустым символом B на каждом конце строки.
Машина Тьюринга M может быть построена следующими способами:
-
Пусть q 0 будет начальным состоянием.
-
Если M находится в q 0 , при чтении 0 он перемещается вправо, входит в состояние q 1 и стирает 0. При чтении 1 он входит в состояние q 2 и перемещается вправо.
-
Если M находится в q 1 , при чтении 0 он перемещается вправо и стирает 0, т. Е. Заменяет 0 на B. Достигнув крайнего левого 1, он входит в q 2 и движется вправо. Если он достигает B, то есть строка содержит только 0, она перемещается влево и входит в состояние q 3 .
-
Если M находится в q 2 , при чтении 0 или 1 он перемещается вправо. Достигнув B, он двигается влево и входит в состояние q 4 . Это подтверждает, что строка содержит только 0 и 1.
-
Если M находится в q 3 , он заменяет B на 0, перемещается влево и достигает конечного состояния q f .
-
Если M находится в q 4 , при чтении 0 или 1 он перемещается влево. По достижении начала строки, т. Е. Когда она читает B, она достигает конечного состояния q f .
Пусть q 0 будет начальным состоянием.
Если M находится в q 0 , при чтении 0 он перемещается вправо, входит в состояние q 1 и стирает 0. При чтении 1 он входит в состояние q 2 и перемещается вправо.
Если M находится в q 1 , при чтении 0 он перемещается вправо и стирает 0, т. Е. Заменяет 0 на B. Достигнув крайнего левого 1, он входит в q 2 и движется вправо. Если он достигает B, то есть строка содержит только 0, она перемещается влево и входит в состояние q 3 .
Если M находится в q 2 , при чтении 0 или 1 он перемещается вправо. Достигнув B, он двигается влево и входит в состояние q 4 . Это подтверждает, что строка содержит только 0 и 1.
Если M находится в q 3 , он заменяет B на 0, перемещается влево и достигает конечного состояния q f .
Если M находится в q 4 , при чтении 0 или 1 он перемещается влево. По достижении начала строки, т. Е. Когда она читает B, она достигает конечного состояния q f .
Следовательно,
M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}
где δ определяется как —