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)