RE to FA: Completion 5/5
• Input: RE r over S
• Output: FA M such that L(r) = L(M)
• Method:
• From “inside” of r, repeatedly use the next
   rules to construct M:
• for RE Æ, construct FA MÆ 
• for RE e, construct FA Me 
• for RE a Ξ S, construct FA Ma
• let for REs r and t, there already exist FAs Mr and
   Mt, respectively; then,
• for RE r.t, construct FA Mr.t     (see 2/5)
• for RE r + t, construct FA Mr + t   (see 3/5)
• for RE r* construct FA Mr*     (see 4/5)
(see 1/5)
25/29