Машина Тьюринга, чтобы проверить, является ли данная строка четным палиндромом или нет

Строка w называется палиндромом, если чтение w слева направо дает тот же результат, что и чтение w справа налево. Четный палиндром имеет четное количество символов.

Примеры:

 Ввод: абааба 
Выход: ДА

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

Ввод: аббаба
Выход: НЕТ

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

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

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

Основная идея :
Головка ленты считывает крайний левый символ w, удаляет этот символ и «запоминает» его посредством состояния. Затем головка ленты перемещается к крайнему правому символу и проверяет, равен ли он (уже удаленному) крайнему левому символу.

Если они равны, то крайний правый символ удаляется, головка ленты перемещается к новому крайнему левому символу, и весь процесс повторяется. В противном случае машина не может достичь конечного состояния, и строка будет отклонена.

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

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

• Шаг 1:
  Мы начинаем с состояния Q0, если мы получаем символ «а» в качестве входных данных, тогда в конце строки также должен быть «а», тогда только строка является палиндромом, и мы должны это проверить. Сначала мы делаем текущий ввод от «a» до B пустым и переходим в состояние Q1, перемещаясь вправо, чтобы пройти по строке, пока не дойдем до конца. Оставьте входные символы a или b, в зависимости от того, какие способы должны быть оставлены без изменений.

  Мы можем дойти до конца строки, когда в качестве входного символа выберем Blank, затем изменим состояние на Q2 и проверим, является ли предыдущий символ «a», затем мы перейдем в состояние Q3, и только тогда мы заменим его пустым, и у нас будет успешно протестировано, что строка является палиндромом до этого момента, теперь мы будем перемещаться назад или влево (сохраняя неизменными a и b, которые встречаются) по строке, пока мы не получим Blank, который является символом, который мы сделали пустым в начале, и мы изменим состояние к Q0. Теперь мы повторяем ту же процедуру для «b» в качестве входных данных.

• Шаг 2:
  До этого момента, если бы строка была палиндромом, она вернулась бы в состояние Q0 после всех итераций, и если бы строка не была палиндромом, мы бы застряли в состояниях Q2 или Q5, и, застряв в этих точках, мы не могли бы достичь Q0 и, следовательно, не можем. достичь конечного состояния или состояния приемки Q7.
• Шаг 3:
  Если строка была палиндромом, то останется только пустой символ, и, следовательно, мы проверяем ее в Q0, если мы получим пустую строку, следовательно, строка будет принята и является палиндромом, в этот момент включено еще одно условие, которое имеет нулевую строку или поскольку пустая строка также является палиндромом, следовательно, принимается.

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