[Overview] [Previous] [Next]

Formal Definition of NFAs

The extension of our notation to NFAs is somewhat strained.

A nondeterministic finite acceptor or nfa is defined by the quintuple

M = (Q, sigma, delta, q0, F)
where These are all the same as for a dfa except for the definition of delta: The language defined by nfa M is defined as
L(M) = {w is a member of sigmastar: deltastar(q0, w) intersection F not equal to null set}

Copyright 1996 by David Matuszek
Last modified Jan 29, 1996