[Overview] [Previous] [Next]

Formal Definition of a DFA

Important! A deterministic finite acceptor or dfa is a quintuple:
M = (Q, sigma, delta, q0, F)
where Note: The fact that delta is a function implies that every vertex has an outgoing arc for each member of sigma.

We can also define an extended transition function deltastar as

deltastar: Q cross product sigmastar goes to Q.


If a DFA M = (Q, sigma, delta, q0, F) is used as a membership criterion, then the set of strings accepted by M is a language. That is,
L(M) = {w is a member of sigmastar: deltastar(q0, w) is a member of F}.

Important! Languages that can be defined by dfas are called regular languages.




Copyright 1996 by David Matuszek
Last modified Jan 29, 1996