Pushdown Automata для Palindrones

Question

Итак, я нашел этот КПК для принятия палиндромов на языке {0,1} *.

Однако, я не в состоянии понять, как он мог мог принять '1' или '0'.

В B он может читать 1 или 0 и нажимать один и тот же символ в стек, а затем перейти к C. Однако, как только он находится в C, ему некуда идти, чтобы добраться до $ в стеке, нужно прочитать еще один символ.

Может кто-нибудь объяснить, как это работает?

Я думаю, что для принятия единственного символа нам понадобится переход от B к D =>1,$->ε | 0,$->ε.

Я был бы прав?

Спасибо :)

Answer 1

Вы правы. Этот КПК не будет принимать 0 или 1 (или, в более общем случае, любой нечетной длины палиндром - вы видите, почему?)

Чтобы исправить это, я бы рекомендовал добавить эти переходы от B к C:

0, & epsilon; &правая стрелка; & Эпсилон;

1, & epsilon; &правая стрелка; & Эпсилон;

Эти переходы по существу позволяют вам употреблять символ «бесплатно». Если вы выбираете среднего персонажа, а строка - палиндром, отлично! Тогда вы примете. Если вы выберете неправильный символ или строка не является палиндром, вы никогда не сможете пройти через состояния C и D, не умирая от автоматов.