Как пуш-автомат знает, как читать палиндром?

Question

Например, как КПК узнает, как читать палиндром в L = {a, b}*?

КПК, который принимает палиндромы через {a,b}*:

Итак, исходя из моего рисунка КПК:

Как он узнает, когда первая половина строки находится на последнем терминале (буква алфавита), и, следовательно, знает, как переходить из состояния 0 в состояние 1 (и, кроме того, знает, что "выталкивает" буквы из стека назад, создавая, таким образом, создавая палиндром)?

Answer 1

Это недетерминированный пуш-ап автомат. Ответ на ваш вопрос заключается в том, что он угадывает и может предположить, что правильно угадать. Недетерминированные автоматы принимают строку w, если любой путь, по которому может быть обработан w, приводит к тому, что w принимается.

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

• он помещает некоторые вещи в стек в состоянии q0
• в конце концов он догадывается, что ему нужно прочитать вторую половину строки
• он читает то, что положил в стек, но в обратном порядке, в q1

Есть три "предположения", которые делает NPDA:

1. он догадывается, что строка является палиндромом четной длины, когда она угадывает ee/e, где e используется вместо лямбды.
2. он догадывается, что строка представляет собой палиндром нечетной длины с a между двумя половинами, когда он угадывает ae/e, где e используется вместо лямбды
3. он предполагает, что строка является палиндромом нечетной длины с буквой b между двумя половинами, когда она предполагает, что / е, где е используется вместо лямбды

Каждое из трех приведенных выше предположений также предполагает, что первая половина строки, исключая возможный средний элемент, уже видна.

Это предположение, в конечном счете, будет верным для любого палиндрома, и не будет верным ни для чего, кроме палиндрома, поэтому NPDA принимает PAL.