Создайте NPDA для языка

Наша стратегия может быть такой:

• введите a, стек a / Z: нажмите a
• ввод a, стек b: pop
• вход b, стек a: pop
• вход b, стек b / Z: нажмите b
• принять, если нет дополнительного ввода и сложить a / 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 с пустым стеком, если во входной строке не меньше a, чем b.