Mr*:
• Let r be a RE over S and Mr = (Qr, S, Rr, sr, {fr}) be
   an FA such that L(Mr) = L(r).
• For the RE r*, there exists an equivalent FA Mr* 
Proof:  Let s, f Ï Qr.
Mr* = (Qr È {s, f}, S, Rr
fr
...
Mr:
sr
s
f
{f})
e
fr ® f,
e
fr ® sr,
e
s ® f },
s,
fr
È {s ® sr,
e
RE to FA: Iteration 4/5
24/29
Construction: