Постройте машину Тьюринга для языка L = {02n1n | n> = 0}

Опубликовано: 17 Февраля, 2022

Предпосылка - машина Тьюринга

Язык L = {0 2n 1 n | n> = 0} представляет собой разновидность языка, в котором мы используем только 2 символа, то есть 0 и 1. В начальном языке есть некоторое количество нулей, за которыми следует ровно половина единиц. Любая такая строка, которая попадает в эту категорию, будет принята этим языком.

Примеры :

 Ввод: 001
Выход: ДА

Ввод: 00001
Выход: НЕТ 

Вход :  или пустая строка
Выход: ДА

Базовое представление -

Начало вычисления:
Лента содержит входную строку w, головка ленты находится на крайнем левом символе w, а машина Тьюринга находится в начальном состоянии Q0.

Основная идея :
Головка ленты считывает крайний левый символ w, который равен 0, и делает пустым, затем следующий крайний слева 0 становится пустым, после чего мы переходим к крайнему правому 1 в строке и делаем его пустым. В n-м способе мы уменьшили строку до 0 2n-2 1 n-1. Если строка принадлежит языку L, то в конце останется пустая строка и, следовательно, будет принята машиной.

Значение используемых символов:
R, L - направление движения одного юнита в обе стороны.
Б-Бланк.
0, 1 - символы, комбинационная строка которых подлежит проверке.

Порядок работы:

  • Шаг 1:
    Как мы знаем, в начале строки будет вдвое больше нулей, чем единиц. Итак, сначала сделаем первые два нуля пустыми и перейдем из состояния Q0 в Q1 и из состояния Q1 в Q2.
  • Шаг 2:
    Сделав их пустыми, мы перейдем к концу строки, пока не получим крайний правый 1 в состоянии Q3 и сделаем его пустым, достигнув состояния Q4.
  • Шаг 3:
    Теперь мы вернемся назад, пока не получим крайний левый ноль в строке, и вернемся в состояние Q0 из Q4.
  • Шаг 4:
    Мы просто сокращаем строку, делая два крайних левых нуля пустыми, а крайние правые 1 - пустыми, и если строка принадлежит языку, она останется пустой и, следовательно, будет принята в состоянии Q5, которое является конечным состоянием. Если строка пуста, она также будет принята в Q5.

Вниманию читателя! Не переставай учиться сейчас. Ознакомьтесь со всеми важными концепциями теории CS для собеседований по SDE с помощью курса теории CS по доступной для студентов цене и будьте готовы к работе в отрасли.

РЕКОМЕНДУЕМЫЕ СТАТЬИ