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

picture of automaton

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

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

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.

Copyright 1996 by David Matuszek
Last modified Jan 29, 1996