Java Reference
In-Depth Information
b
a
b
1
2
3
Original Automaton
a
a | b
4
b
λ
a
b
0
1
2
3
λ
a
5
New Automaton with Start
and Accepting States Added
a | b
λ
4
Figure 3.29: An FA with new start and accepting states added.
So far, we have concentrated on the process of converting a given regular
expression into an equivalent FA. This is the key step in Lex's construction of
a scanner from a set of regular expression token patterns.
Since regular expressions, DFAs, and NFAs are interconvertible, it is also
possible to derive for any FA a regular expression that describes the strings
that the FA matches. In this section, we briefly discuss an algorithm that does
this derivation. This algorithm is sometimes useful when you already have
an FA you want to use but you need a regular expression to program Lex or
to describe the FA's e
ect. This algorithm also helps you to see that regular
expressions and FAs really are equivalent.
The algorithm we use is simple and elegant. We start with an FA and
simplify it by removing states, one by one. Simplified FAs are equivalent to
the original, except that transitions are now labeled with regular expressions
rather than individual characters. We continue removing states until we have
an FA with a single transition from the start state to a single accepting state.
The regular expression that labels that single transition correctly describes the
e
ff
ect of the original FA.
To start, we assume our FA has a start state with no transitions into it and
a single accepting state with no transitions out of it. If it fails to meet these
ff
