Accepting Strings with an NPDA (Formal Version)

We have the notation "

" to indicate a single move of an npda. We will also use "

" to indicate a sequence of zero or more moves, and we will use "

" to indicate a sequence of one or more moves.

If M = (Q, , , , q₀, z, F) is an npda, then the language accepted by M, L(M), is given by

L(M) = {w

*: (q₀, w, z)

(p,

, u), p

F, u

*}.

You should understand this notation.