Нам нужен стек для (a), потому что мы должны помнить, сколько a мы видели спереди, чтобы мы могли убедиться, что у нас такое же число сзади. КПК для этого может поместить sh a в стек, пока не увидит первый b; затем он может читать буквы b; затем он может читать оставшиеся «а», выталкивая из стека один к одному, пока не закончатся входные данные. Если КПК увидел одинаковое количество букв «а» спереди и сзади, то в конце стопка должна быть пустой; КПК может распознать, истинно ли это, и принять, если это так, в противном случае отклонить.
Состояние q0: on a, pu sh a в стеке и go состояние q0; на b, go в положение q1. Состояние q1: на a, вытолкнуть a из стека и go в состояние q2; на b оставьте стек в покое и go в состоянии q1 Состояние q2: на a вытолкните a из стека и go в состояние q2; on b, cra sh и отклонить входное условие Accept: в состоянии q2 вход исчерпан и пустой стек
Для номера 2 мы можем использовать стек, чтобы вести текущий счет баланса не-b vs b мы уже видели. Мы начинаем с чтения и вставки в стек; когда мы начинаем читать b, мы выталкиваем a из стека, пока не кончимся, затем мы начинаем нажимать b. Как только мы начинаем читать c, мы выталкиваем b из стека, пока стек не станет пустым, а затем начинаем нажимать c. Мы принимаем ввод, если стек пуст (это означает, что мы видели такое же количество non-b, что и b), и отклоняем в противном случае.
State q0: on a, pu sh a в стек , оставайтесь в q0; на b вставьте a (если есть) или pu sh b (если пустой стек) и go для состояния q1. на c, cra sh и отклонить
Состояние q1: на a, cra sh и отклонить; на b вставьте a (если есть) или pu sh b (если стек пуст) и оставайтесь в q1; on c, pop b (если есть) или pu sh c в противном случае и go для состояния q2.
State q2: on a или b, cra sh и отклонить; on c, pop b (если есть) или pu sh c в противном случае, и оставаться в q2.
Условие принятия: в состоянии q2 ввод исчерпан и стек пуст.