• 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