Mr.t:
RE to FA: Concatenation 2/5
• 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 a RE over S and Mt = (Qt, S, Rt, st, {ft}) be
   an FA  such that L(Mt) = L(t).
• Then, for the RE r.t, there exists an equivalent FA Mr.t
Proof: Let Qr Ç Qt = Æ.
Mr.t = (Qr È Qt, S, Rr È Rt
fr
ft
...
Mr:
sr
...
Mt:
st
fr
ft
sr,
È {fr ® st},
e
{ft})
22/29
Construction: