The difference is that, in this automaton,
does not appear to be a function. It looks like a *partial function*, that
is, it is not defined for all values of Q.

We can complete the definition of by assuming the existence of an "invisible" state and some "invisible" arcs. Specifically,

- There is exactly one implicit
*error state*; - If there is no path shown from a state for a given symbol in , there is an implicit path for that symbol to the error state;
- The error state is a
*trap state*: once you get into it, all arcs (one for each symbol in ) lead back to it; and - The error state is not a final state.

I don't think you'll find abbreviated automata in the textbook.
They aren't usually allowed in a formal course.
However, if you ever use an automaton to design a
lexical scanner, putting in an explicit error state
just clutters up the diagram.

Copyright © 1996 by David Matuszek

Last modified Jan 29, 1996