[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 , we can label arcs with a/x,y where a, x, and y*.

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

(Q={q₀,q₁,q₂,q₃},

={a,b},

={0,1},

, q₀, z=0, F={q₃}) where

(q₀, a, 0) = {(q₁, 10), (q₃,

)}

(q₀,

, 0) = {(q₃,

)}

(q₁, a, 1) = {(q₁, 11)}

(q₁, b, 1) = {(q₂,

)}

(q₂, b, 1) = {(q₂,

)}

(q₂,

, 0) = {(q₃,

)}

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 to .