[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" 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.

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.

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.