[Overview] [Previous] [Next]

Drawing NPDAs

NPDAs are not usually drawn. However, with a few minor extensions, we can draw an npda similar to the way we draw an nfa.

Instead of labeling an arc with an element of sigma, we can label arcs with a/x,y where ais a member ofsigma, xis a member ofgamma, and yis a member ofgamma*.

Consider the following npda (example 7.2 on page 186 in your textbook).

(Q={q0,q1,q2,q3}, sigma={a,b}, gamma={0,1}, delta, q0, z=0, F={q3})
where
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)}

This npda can be drawn as
drawing of an npda

Note: the top of the stack is considered to be to the left, so that, for example, if we get an a from the starting position, the stack changes from (top) 0 (bottom) to (top) 1 0 (bottom).


Copyright 1996 by David Matuszek
Last modified Mar 3, 1996