На ум приходят два подхода:
- попытаться написать КПК с нуля, используя стек разумным способом
- написать CFG, а затем положиться на конструкцию это показывает, что КПК принимают языки всех CFG
. Для использования подхода 1 следует признать, что КПК подобны NFA, которые могут помещать символы sh в стек и извлекать их. Если мы хотим, чтобы 2n> = m, это означает, что мы хотим, чтобы число a было не менее половины числа b. То есть мы хотим иметь хотя бы один a на каждые два b. Это означает, что если мы наберем sh всех a в стеке, нам нужно прочитать не более двух b для каждого a в стеке. Это предполагает, что КПК работает следующим образом:
1. read all the a's, pushing into the stack
2. read b's, popping an a for every two b's you see
3. if you run out of stack but still have b's to process, reject
4. if you run out of input at the same time or sooner than you run out of stack, accept
В терминах состояний и переходов:
Q S E Q' S'
q0 Z a q0 aZ // these transitions read all the a's and
q0 a a q0 aa // push them onto the stack
q0 a b q1 a // these transitions read all the b's and
q1 a b q2 - // pop a's off the stack for every complete
q2 a b q1 a // pair of b's we see. if we run out of a's
// it will crash and reject
q0 Z - q3 Z // these transitions just let us guess at any
q0 a - q3 a // point that we have read all the input and
q1 Z - q3 Z // go to the accepting state. note that if
q1 a - q3 a // we guessed wrong the PDA will crash there
q2 Z - q3 Z // since we have no transitions defined.
q2 a - q3 a // crashing rejects the input.
Здесь условие принятия находится в состоянии q3 без стека.
Чтобы сделать второй вариант, вы должны написать CFG следующим образом:
S -> aSbb | aS | e
Тогда ваш КПК может сделать следующее:
push S onto the stack
pop from the stack and push onto the stack one of the productions for S
if you pop a terminal off the stack, consume the nonterminal from input
if you pop a nonterminal off the stack, replace it with some production for that nonterminal
Это недетерминированное генерирование каждого возможный вывод по CFG. Если входные данные являются строкой на языке, то один из этих производных будет использовать все входные данные и оставит стек пустым, что является условием остановки / принятия.