[Overview] [Previous] [Next]
Abbreviated Acceptor for Ada Identifiers
The following is an abbreviated automaton (my terminology)
to recognize Ada identifiers.
You might use something like this in a course on compiler construction.
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"
The automaton represented above is really exactly the same
as the automaton on the previous page;
we just haven't bothered to draw one state and a whole bunch of arcs
that we know must be there.
- 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