Para quaisquer linguagens regulares
L
1
{\displaystyle L_{1}}
L
2
{\displaystyle L_{2}}
L
1
∪
L
2
{\displaystyle L_{1}\cup L_{2}}
Prova
Uma vez que
L
1
{\displaystyle L_{1}}
L
2
{\displaystyle L_{2}}
AFNs
N
1
,
N
2
{\displaystyle N_{1},\ N_{2}}
L
1
{\displaystyle L_{1}}
L
2
{\displaystyle L_{2}}
Seja
N
1
=
(
Q
1
,
Σ
,
T
1
,
q
1
,
A
1
)
{\displaystyle N_{1}=(Q_{1},\ \Sigma ,\ T_{1},\ q_{1},\ A_{1})}
N
2
=
(
Q
2
,
Σ
,
T
2
,
q
2
,
A
2
)
{\displaystyle N_{2}=(Q_{2},\ \Sigma ,\ T_{2},\ q_{2},\ A_{2})}
Vamos construir
N
=
(
Q
,
Σ
,
T
,
q
0
,
A
1
∪
A
2
)
{\displaystyle N=(Q,\ \Sigma ,\ T,\ q_{0},\ A_{1}\cup A_{2})}
onde
Q
=
Q
1
∪
Q
2
∪
{
q
0
}
{\displaystyle Q=Q_{1}\cup Q_{2}\cup \{q_{0}\}}
T
(
q
,
x
)
=
{
T
1
(
q
,
x
)
se
q
∈
Q
1
T
2
(
q
,
x
)
se
q
∈
Q
2
{
q
1
,
q
2
}
se
q
=
q
0
e
x
=
ϵ
∅
se
q
=
q
0
e
x
≠
ϵ
{\displaystyle T(q,x)=\left\{{\begin{array}{lll}T_{1}(q,x)&{\mbox{se}}&q\in Q_{1}\\T_{2}(q,x)&{\mbox{se}}&q\in Q_{2}\\\{q_{1},q_{2}\}&{\mbox{se}}&q=q_{0}\ e\ x=\epsilon \\\emptyset &{\mbox{se}}&q=q_{0}\ e\ x\neq \epsilon \end{array}}\right.}
Em seguida, vamos usar
p
→
x
,
T
q
{\displaystyle p{\stackrel {x,T}{\rightarrow }}q}
q
∈
E
(
T
(
p
,
x
)
)
{\displaystyle q\in E(T(p,x))}
Seja
w
{\displaystyle w}
L
1
∪
L
2
{\displaystyle L_{1}\cup L_{2}}
w
∈
L
1
{\displaystyle w\in L_{1}}
Seja
w
=
x
1
x
2
⋯
x
m
{\displaystyle w=x_{1}x_{2}\cdots x_{m}}
m
≥
0
,
x
i
∈
Σ
{\displaystyle m\geq 0,x_{i}\in \Sigma }
Uma vez que
N
1
{\displaystyle N_{1}}
x
1
x
2
⋯
x
m
{\displaystyle x_{1}x_{2}\cdots x_{m}}
r
0
,
r
1
,
⋯
r
m
∈
Q
1
{\displaystyle r_{0},r_{1},\cdots r_{m}\in Q_{1}}
q
1
→
ϵ
,
T
1
r
0
→
x
1
,
T
1
r
1
→
x
2
,
T
1
r
2
⋯
r
m
−
1
→
x
m
,
T
1
r
m
,
r
m
∈
A
1
{\displaystyle q_{1}{\stackrel {\epsilon ,T_{1}}{\rightarrow }}r_{0}{\stackrel {x_{1},T_{1}}{\rightarrow }}r_{1}{\stackrel {x_{2},T_{1}}{\rightarrow }}r_{2}\cdots r_{m-1}{\stackrel {x_{m},T_{1}}{\rightarrow }}r_{m},r_{m}\in A_{1}}
Desde que
T
1
(
q
,
x
)
=
T
(
q
,
x
)
∀
q
∈
Q
1
∀
x
∈
Σ
{\displaystyle T_{1}(q,x)=T(q,x)\ \forall q\in Q_{1}\forall x\in \Sigma }
r
0
∈
E
(
T
1
(
q
1
,
ϵ
)
)
⇒
r
0
∈
E
(
T
(
q
1
,
ϵ
)
)
{\displaystyle r_{0}\in E(T_{1}(q_{1},\epsilon ))\Rightarrow r_{0}\in E(T(q_{1},\epsilon ))}
r
1
∈
E
(
T
1
(
r
0
,
x
1
)
)
⇒
r
1
∈
E
(
T
(
r
0
,
x
1
)
)
{\displaystyle r_{1}\in E(T_{1}(r_{0},x_{1}))\Rightarrow r_{1}\in E(T(r_{0},x_{1}))}
⋮
{\displaystyle \vdots }
r
m
∈
E
(
T
1
(
r
m
−
1
,
x
m
)
)
⇒
r
m
∈
E
(
T
(
r
m
−
1
,
x
m
)
)
{\displaystyle r_{m}\in E(T_{1}(r_{m-1},x_{m}))\Rightarrow r_{m}\in E(T(r_{m-1},x_{m}))}
T
{\displaystyle T}
T
1
{\displaystyle T_{1}}
q
1
→
ϵ
,
T
r
0
→
x
1
,
T
r
1
→
x
2
,
T
r
2
⋯
r
m
−
1
→
x
m
,
T
r
m
,
r
m
∈
A
1
∪
A
2
,
r
0
,
r
1
,
⋯
r
m
∈
Q
{\displaystyle q_{1}{\stackrel {\epsilon ,T}{\rightarrow }}r_{0}{\stackrel {x_{1},T}{\rightarrow }}r_{1}{\stackrel {x_{2},T}{\rightarrow }}r_{2}\cdots r_{m-1}{\stackrel {x_{m},T}{\rightarrow }}r_{m},r_{m}\in A_{1}\cup A_{2},r_{0},r_{1},\cdots r_{m}\in Q}
T
(
q
0
,
ϵ
)
=
{
q
1
,
q
2
}
⇒
q
1
∈
T
(
q
0
,
ϵ
)
⇒
q
1
∈
E
(
T
(
q
0
,
ϵ
)
)
⇒
q
0
→
ϵ
,
T
q
1
{\displaystyle {\begin{array}{lcl}T(q_{0},\epsilon )=\{q_{1},q_{2}\}&\Rightarrow &q_{1}\in T(q_{0},\epsilon )\\\\&\Rightarrow &q_{1}\in E(T(q_{0},\epsilon ))\\\\&\Rightarrow &q_{0}{\stackrel {\epsilon ,T}{\rightarrow }}q_{1}\end{array}}}
e
q
0
→
ϵ
,
T
q
1
→
ϵ
,
T
r
0
⇒
q
0
→
ϵ
,
T
r
0
{\displaystyle q_{0}{\stackrel {\epsilon ,T}{\rightarrow }}q_{1}{\stackrel {\epsilon ,T}{\rightarrow }}r_{0}\Rightarrow q_{0}{\stackrel {\epsilon ,T}{\rightarrow }}r_{0}}
q
0
→
ϵ
,
T
r
0
→
x
1
,
T
r
1
→
x
2
,
T
r
2
⋯
r
m
−
1
→
x
m
,
T
r
m
,
r
m
∈
A
1
∪
A
2
,
r
0
,
r
1
,
⋯
r
m
∈
Q
{\displaystyle q_{0}{\stackrel {\epsilon ,T}{\rightarrow }}r_{0}{\stackrel {x_{1},T}{\rightarrow }}r_{1}{\stackrel {x_{2},T}{\rightarrow }}r_{2}\cdots r_{m-1}{\stackrel {x_{m},T}{\rightarrow }}r_{m},r_{m}\in A_{1}\cup A_{2},r_{0},r_{1},\cdots r_{m}\in Q}
N
{\displaystyle N}
x
1
x
2
⋯
x
m
{\displaystyle x_{1}x_{2}\cdots x_{m}}
Nota: A ideia extraída desta prova matemática para construção de uma máquina para reconhecer
L
1
∪
L
2
{\displaystyle L_{1}\cup L_{2}}
L
1
{\displaystyle L_{1}}
L
2
{\displaystyle L_{2}}
ϵ
{\displaystyle \epsilon }
