[Overview] [Previous] [Next]

Example NPDA Execution

Consider the following npda:
drawing of an npda
delta(q0, a, 0) = {(q1, 10), (q3, empty string)}
delta(q0, empty string, 0) = {(q3, empty string)}
delta(q1, a, 1) = {(q1, 11)}
delta(q1, b, 1) = {(q2, empty string)}
delta(q2, b, 1) = {(q2, empty string)}
delta(q2, empty string, 0) = {(q3, empty string)}


We can recognize the string aaabbb by the following sequence of moves:

(q0, aaabbb, 0)
move to (q1, aabbb, 10)
move to (q1, abbb, 110)
move to (q1, bbb, 1110)
move to (q2, bb, 110)
move to (q2, b, 10)
move to (q2, empty string, 0)
move to (q3, empty string, empty string).
Since q3 is a member of F, the string is accepted.


Copyright 1996 by David Matuszek
Last modified Mar 7, 1996