• For
a RE r = Æ, there is an
equivalent FA MÆ.
• For
a RE r = e, there is an
equivalent FA Me .
• For a RE r = a, a
Î S, there is an
equivalent FA Ma .
a
Proof: MÆ :
Proof: Me :
s
s
f
Proof: Ma :
e
s
f
Conversion
of RE to FA: Basics 1/5
Algorithm that converts any RE to an equivalent FA (lex in UNIX).
Gist:
21/29