Недетерминированные пушдаунные автоматы и палиндром

Question

Мне нужно найти палиндромы в тексте (слова имеют длину <= 6 и состоят из строчных и прописных букв) и использовать для этого автоматы Pushdown, но, к сожалению, я не совсем знаком с этой темой. Может ли кто-нибудь объяснить мне, как я могу запрограммировать это? Или, может быть, какая-то статья или темы, где это было сделано. Буду рад каждому совету!

Answer 1

Простым подходом может быть добавление флага в середине вашего слова. Начните вставлять каждый символ вашего слова в стек, пока не дойдете до флага. Достигнув флага, вы начинаете выталкивать персонажа из стека и сравнивать его со второй половиной своего слова.

Если каждый символ в стеке совпадает с каждым соответствующим символом во второй половине, ваше слово - палиндром. Это простое решение, если вы понимаете это, вы также можете провести дополнительные исследования для решения без флага.

Кроме того, я думаю, что ваша лучшая карта - взглянуть на другие ответы, такие как: Как автомат с автоматическим управлением знает, как читать палиндром? это очень хорошо объясняет, как автоматы работают с любой длиной палиндрома (четная и нечетная длина), поскольку мое решение будет работать только с четной длиной.