На самом деле это довольно просто. Каждый раз, когда вы читаете «ab», вы сохраняете токен в стеке. Затем, прочитав «c», вы берете один из этого токена. Затем за каждый «бб» вы берете один жетон из стека. Когда стек пуст, вы соглашаетесь.
Для самого NPDA все зависит от того, как вы определяете приемку. Из вашего вопроса я не понимаю, что вы имеете в виду под «написать a, а затем двигаться вправо». Вы путаете NPDA с машиной Тьюринга? NPDA очень похож на NFA (недетерминированные конечные автоматы), за исключением того, что он оснащен стеком, в который вы можете помещать символы стека. Подробнее читайте здесь: http://www.cs.duke.edu/~rodger/courses/cps140/lects/sectnpdaH.pdf
Ниже приведена таблица переходов, предполагающая символы стека {A,Z}, где Z — начальный символ стека. Принять, когда мы находимся в единственном принимающем состоянии qa и мы закончили чтение входной ленты. Предположим, что каждый переход всегда потребляет один символ стека, и если нет больше символа, который нужно использовать, пока NPDA не находится в состоянии принятия, NPDA не принимает (или отклоняет) строку.
В приведенной ниже таблице первый столбец представляет состояние, в котором мы сейчас находимся, и символ стека, который мы читаем. Последующие столбцы представляют новое состояние и символ стека, помещаемый в стек при чтении определенного символа во входной строке (или вообще без чтения какого-либо символа с помощью ε).
+------++---------+-------+--------+-------+
| || a | b | c | ε |
+------++---------+-------+--------+-------+
|(q1,Z)|| (q2,Z) | - | - | - |
+------++---------+-------+--------+-------+
|(q1,A)|| (q2,A) | - | (q3,ε) | - |
+------++---------+-------+--------+-------+
|(q2,Z)|| - |(q1,ZA) | - | - |
+------++---------+-------+--------+-------+
|(q2,A)|| - |(q1,AA) | - | - |
+------++---------+-------+--------+-------+
|(q3,Z)|| - | - | - |(qa,ε) |
+------++---------+-------+--------+-------+
|(q3,A)|| - | (q4,A) | - | - |
+------++---------+-------+--------+-------+
|(q4,A)|| - | (q3,ε) | - | - |
+------++---------+-------+--------+-------+
Ключевая идея здесь заключается в том, что количество букв A в стеке показывает, сколько раз фраза «ab» появляется во входной строке.
Вы можете видеть, что при чтении "a" в состоянии q1 с символом стека Z мы помещаем Z обратно в стек. Это означает, что "ab" еще не обнаружен. Затем он перейдет к q2.
В q2 мы принимаем только «b», любой другой ввод приведет к зависанию (и, следовательно, отклонению). Он помещает считанное состояние обратно в стек, а также дополнительный A, эффективно увеличивая количество A в стеке на 1, поскольку этот переход представляет собой дополнительную фразу «ab» во входной строке.
Состояние q3 представляет часть после успешного чтения "c". Обратите внимание, что переход от q1 к q3 должен потреблять A, а не Z, так как у нас есть ограничение n >= 1. Затем, прочитав «b», он перейдет в состояние q4, чтобы дождаться другого «b». Позже q4, при чтении "b", будет потреблять символ стека A, соответствующий
В состоянии q3 нам также нужен переход в состояние принятия qa, как только мы достигнем символа стека Z, ссылаясь на состояние, в котором есть n копий "ab" и n-1 копии "бб".
Состояние q4 принимает только входную строку "b" с символом стека A, что означает, что новая фраза "bb" должна совпадать с ранее найденной фразой "ab".
Надеюсь это поможет!
person
justhalf
schedule
28.11.2013
