Постройте машину Тьюринга для языка L = {a ^ nb ^ mc ^ nm, где n> = 0 и m> = 0}
Предпосылка - машина Тьюринга
Язык 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 по доступной для студентов цене и будьте готовы к работе в отрасли.