Постройте машину Тьюринга для языка L = {a ^ nb ^ mc ^ nm, где n> = 0 и m> = 0}

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

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

Язык L = {a n b m c nm | n> = 0 и m> = 0} представляет собой разновидность языка, в котором мы используем только 3 символа, то есть a, b и c. В начале в языке есть n чисел, за которыми следуют m чисел b, а затем n * m чисел c. Любая такая строка, которая попадает в эту категорию, будет принята этим языком.

Примеры:

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

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

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

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

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

Основная идея :
Головка ленты считывает крайний левый символ w, который является a, и только в начале мы сделаем его пустым. Затем мы будем перемещаться, чтобы сделать крайний левый ba $ и заменить крайний правый c пустым, мы будем делать этот зигзагообразный шаблон замены b на $ и c на Blank, пока все b не будут заменены на $. После этого мы вернемся в левом направлении пока мы не дойдем до крайнего левого угла a и не заменим все $ на b в обходе. После этого мы уменьшили нашу строку до формы a n-1 b m c nm-m, чтобы мы могли понять, заменены ли все a пустыми, и если строка принадлежит языку L, тогда не останется c, поэтому она будет принята.

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

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

  • Шаг 1:
    Сначала мы заменяем крайний левый a на Blank, а затем перемещаемся, чтобы заменить крайний левый b на $ и крайний правый c на Blank. Повторяйте этот шаг от состояния Q1 до тех пор, пока b не останется больше.
  • Шаг 2:
    После замены всех b на $ мы также заменили m крайних правых c на пробелы, а затем вернемся к самому левому a и заменим все $ на b. После этого шага, если проверить строку, она теперь уменьшается до n-1 b m c nm-m. Теперь мы будем повторять с шага 1, пока все a не станут пустыми.
  • Шаг 3:
    Итак, после того, как все a сделаны пустыми, и если строка принадлежит языку L, тогда должно быть оставлено 0 c, которые мы проверяем в состоянии Q0 и Q6, так как останутся только b, и после чего, если будет найдено пустое значение, все c должны быть заменены на Пусто, так как мы делали пробел c с самого правого конца строки.
  • Шаг 4:
    Таким образом, если мы получим пустой символ в состоянии Q6, строка будет принята в конечном состоянии Q7. Также, если строка была пустой, она также будет принята как ввод пустого символа в состоянии Q0, тогда она перейдет в состояние Q7 и будет принята.

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

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