Lexical Analysis - Introduction to Compiler Construction in a Java World - page 39

Example. The reserved words may be described simply by listing them. For example,
abstract
|boolean
|char
.
.
.
|while
Likewise for operators. For example,
=
|==
|>
.
.
.
|*
Identifiers are easily described; for example,
([a-zA-Z]|_|$)([a-zA-Z0-9]|_|$)*
which is to say, an identifier begins with a letter, an underscore, or a dollar sign, followed
by zero or more letters, digits, underscores, and dollar signs.
A full description of the lexical syntax for j-- may be found in Appendix B. In the next
section, we formalize state transition diagrams.
2.4 Finite State Automata
It turns out that for any language described by a regular expression, there is a state transi-
tion diagram that can parse strings in this language. These are called finite state automata.
Denition 2.2. A nite state automaton (FSA) F is a quintuple F = (;S;s 0 ;M;F)
where
(pronounced sigma) is the input alphabet.
S is a set of states.
s 0 2 S is a special start state.
M is a set of moves or state transitions of the form
m(r;a) = s where r;s 2 S;a 2
read as, \if one is in state r, and the next input symbol is a, scan the a and move into
state s."
F 2 S is a set of nal states.
A finite state automaton is just a formalization of the state transition diagrams we saw
in Section 2.2. We say that a finite state automaton recognizes a language. A sentence over
the alphabet is said to be in the language recognized by the FSA if, starting in the start
state, a set of moves based on the input takes us into one of the final states.