Наша стратегия может быть такой:
- ввод a, стек a / Z: push a
- ввод a, стек b: pop
- вход b, стек a: pop
- вход b, стек b / Z: push b
- примите, если нет дополнительного ввода и сложите / Z
Почему это работает? Если у нас больше a, чем b, мы получаем в стеке a. Если числа a и b совпадают, мы получаем Z в стеке. Если b больше, чем a, мы получаем b в стеке. Поэтому мы принимаем либо a, либо Z сверху, когда ввод исчерпан.
q e s q' s'
q0 a Z q0 aZ
q0 a a q0 aa
q0 a b q0 -
q0 b Z q0 bZ
q0 b a q0 -
q0 b b q0 bb
q0 - a q1 a
q0 - Z q1 Z
q1 - a q1 -
Этот КПК заканчивается в q1 пустым стеком, если во входной строке есть по крайней мере столько же, сколько b.