M
r.t
:
RE
to FA: Concatenation 2/5
•
Let
r
be
a
RE over
S
and
M
r
= (
Q
r
,
S
,
R
r
,
s
r
, {
f
r
})
be
an
FA
such that
L
(
M
r
) =
L
(
r
).
•
Let
t
be
a
RE over
S
and
M
t
= (
Q
t
,
S
,
R
t
,
s
t
, {
f
t
})
be
a
n
FA
such that
L
(
M
t
) =
L
(
t
).
•
Then, for the RE
r
.
t
,
t
here exists a
n equivalent
FA
M
r.
t
Proof:
Let
Q
r
Ç
Q
t
=
Æ
.
M
r.t
= (
Q
r
È
Q
t
,
S
,
R
r
È
R
t
f
r
f
t
...
M
r
:
s
r
...
M
t
:
s
t
f
r
f
t
s
r
,
È
{
f
r
®
s
t
},
e
{
f
t
})
22
/2
9
Construction: