Во-первых, мы признаем, что нам нужно принимающее состояние q0. Поскольку epsilon есть в языке, мы можем считать, что q0 принимает (и принимает как пустой стек, так и состояние принятия одновременно). Мы организуем, чтобы q0 представляло состояние КПК всякий раз, когда префикс ввода, который мы обработали до сих пор, имеет сбалансированные скобки и скобки; все строки в языке будут здесь с пустым стеком. Если мы когда-либо находимся в q0 и не видим символ нижней части стека Z0 на вершине стека, мы можем безопасно аварийно завершить работу и отклонить ввод (хотя мы организуем это так, что этого никогда не произойдет).
Если q0 соответствует просмотру строки в языке и поскольку в нем могут присутствовать префиксы, не являющиеся языком, которые, тем не менее, могут вернуться к языку, мы выводим, что нам нужно хотя бы одно дополнительное состояние. Назовите это q1. Мы можем добавить переходы от q0 к q1 либо [или (и поместить их в стек, чтобы мы помнили, что они были. Мы можем пойти дальше и потерпеть крах, если увидим] или) в состоянии q0, так как мы организуем его так, чтобы быть в Состояние q0 означает, что мы видели префикс ввода, который является строкой в языке, и увидеть закрывающие скобки и скобки на таком этапе невозможно исправить.
В состоянии q1 мы видели некоторые открывающие скобки и / или круглые скобки, которые не были сопоставлены с соответствующими закрывающими скобками и / или круглыми скобками. В любой момент мы можем принять открывающие фигурные скобки или круглые скобки, вернувшись к q1 и поместив символы, встречающиеся на вершине стека. Однако, встречая закрывающие скобки, мы должны быть осторожны, чтобы убедиться, что мы подбираем правильные слова Поэтому нам нужны только переходы для обработки совпадающих пар; мы можем потерпеть крах на непревзойденных парах.
Если в состоянии q1 мы смотрим на пустой стек, мы признаем, что мы сопоставили все в текущем сегменте и смотрим на строку в языке; в этом случае мы можем добавить эпсилон-переход обратно к q0.
Готовый КПК выглядит так:
Q s S Q' S'
- - - - -
q0 [ Z0x q1 [Z0x
q0 ( Z0x q1 (Z0x
q1 [ x q1 [x
q1 ( x q1 (x
q1 ] [x q1 x
q1 ) (x q1 x
q1 e Z0 q0 Z0
В вышеприведенном:
e это эпсилон, пустая строка x - произвольная строка над входным алфавитом Z0 - символ нижней части стопки