[Overview] [Previous] [Next]

Accepting Strings with an NPDA (Formal Version)

We have the notation "move to" to indicate a single move of an npda. We will also use "move zero or more times to" to indicate a sequence of zero or more moves, and we will use "move one or more times to" to indicate a sequence of one or more moves.

If M = (Q, sigma, gamma, delta, q0, z, F) is an npda, then the language accepted by M, L(M), is given by

L(M) = {w is a member of sigma*: (q0, w, z) move zero or more times to (p, empty string, u), p is a member of F, u is a member of gamma*}.

You should understand this notation.


Copyright 1996 by David Matuszek
Last modified Mar 7, 1996