• Let r be a RE over S and Mr = (Qr, S, Rr, sr, {fr}) be
an FA such
that L(Mr) = L(r).
• Let t be RE over S and Mt = (Qt, S, Rt, st, {ft}) be
an FA such
that L(Mt) = L(t).
• For a RE r + t, there
exists an equivalent FA Mr+t
Mr+t = (Qr È Qt È {s, f } , S, Rr È Rt
fr
ft
...
Mr:
sr
...
Mt:
st
s
f