Для первого NPDA потребуется два a, затем прочитает a и b (и, по крайней мере, один b) и поместит их в стек, затем прочитает c и выскочит из стека.Если стек пуст и вход исчерпан, машина может его принять.
Q s S Q' S'
-----------------------
q0 a Z q1 Z // read two a
q1 a Z q2 Z
q2 a Z q2 cZ // read all a
q2 a a q2 ca // and at least one b
q2 b Z q3 cZ
q2 b a q3 ca
q3 b c q3 cc // read all b
q3 c c q4 - // and at least one c
q4 c c q4 - // read all c
q4 - Z q5 Z // go to accepting state on empty stack
Для второго NPDA потребуется три a, затем будет читать a и помещать в стек, затем читать b ивыскочить из стека.Если стек пуст и вход исчерпан, машина может принять.
Q s S Q' S'
-----------------------
q0 a Z q1 Z
q1 a Z q2 Z
q2 a Z q3 Z
q3 a Z q3 aZ
q3 a a q3 aa
q3 b a q4 -
q3 - Z q5 Z
q4 b a q4 -
q4 - Z q5 -
Обратите внимание, что и q3, и q4 здесь могут перейти в состояние принятия q5 и принять, если они исчерпали вход и смотрят напустой стек.