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

FIGURE 2.9 Scanning symbol a.
2. If N r and N s are NFA recognizing the languages described by the regular expressions r
and s, respectively, then we can create a new NFA recognizing the language described
by rs as follows. We dene an -move from the nal state of N r to the start state of
N s . We then choose the start state of N r to be our new start state, and the final state
of N s to be our new final state.
FIGURE 2.10 Concatenation rs.
3. If N r and N s are NFA recognizing the languages described by the regular expressions r
and s, respectively, then we can create a new NFA recognizing the language described
by rjs as follows. We dene a new start state, having -moves to each of the start
states of N r and N s , and we dene a new nal state and add -moves from each of
N r and N s to this state.
FIGURE 2.11 Alternation rjs.
4. If N r is an NFA recognizing that language described by a regular expression r, then
we construct a new NFA recognizing r as follows. We add an -move from N r 's nal
state back to its start state. We define a new start state and a new final state, we add
-moves from the new start state to both N r 's start state and the new nal state, and
we dene an -move from N r 's nal state to the new nal state.