Принимаемый язык и выбранный язык

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

TM определяет язык, принимает ли он его, и входит в состояние отклонения для любого ввода не на этом языке. Язык рекурсивен, если он определяется машиной Тьюринга.

В некоторых случаях TM не останавливается. Такая ТМ принимает язык, но не решает его.

Разработка машины Тьюринга

Основные принципы разработки машины Тьюринга были объяснены ниже с помощью пары примеров.

Пример 1

Разработайте TM для распознавания всех строк, состоящих из нечетного числа α.

Solution

Машина Тьюринга M могут быть построены следующими движениями -

  • Позволять q1 быть начальным состоянием.

  • Если M в q1; при сканировании α он переходит в состояниеq2 и пишет B (пусто).

  • Если M в q2; при сканировании α он переходит в состояниеq1 и пишет B (пусто).

  • Из приведенных выше ходов мы видим, что M входит в государство q1 если он просканирует четное число α и перейдет в состояние q2если он сканирует нечетное количество α. Следовательноq2 единственное принимающее государство.

Следовательно,

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.

Solution

Предположим, что входная строка заканчивается пустым символом B на каждом конце строки.

Машина Тьюринга, M, могут быть построены следующими движениями -

  • Позволять q0 быть начальным состоянием.

  • Если M в q0, при чтении 0 он движется вправо, переходит в состояние q1 и стирает 0. При чтении 1 он переходит в состояние q2 и движется вправо.

  • Если M в q1при чтении 0 он перемещается вправо и стирает 0, т. е. заменяет 0 на B. Достигнув крайней левой единицы, он входитq2и движется вправо. Если он достигает B, т. Е. Строка состоит только из нулей, он перемещается влево и переходит в состояниеq3.

  • Если M в q2при чтении 0 или 1 он перемещается вправо. Достигнув B, он перемещается влево и входит в состояниеq4. Это подтверждает, что строка состоит только из нулей и единиц.

  • Если M в q3, он заменяет B на 0, перемещается влево и достигает конечного состояния qf.

  • Если M в q4при чтении 0 или 1 он перемещается влево. Достигнув начала строки, т.е. когда он читает B, он достигает конечного состоянияqf.

Следовательно,

M = {{q 0 , q 1 , q 2 , q 3 , q 4 , q f }, {0,1, B}, {1, B}, δ, q 0 , B, {q f }}

где δ определяется как -

Символ алфавита ленты Текущее состояние 'q 0 ' Текущее состояние 'q 1 ' Текущее состояние 'q 2 ' Текущее состояние 'q 3 ' Текущее состояние 'q 4 '
0 BRq 1 BRq 1 ORq 2 - OLq 4
1 1Rq 2 1Rq 2 1Rq 2 - 1лк 4
B BRq 1 BLq 3 BLq 4 OLq f BRq f