União de duas linguagens regulares

Na teoria das linguagens formais, e em particular na teoria dos autômatos finitos não determinísticos, é conhecido que a união de duas linguagens regulares é uma linguagem regular. Este artigo fornece uma prova desta afirmação.

Teorema

Para quaisquer linguagens regulares $L_1$ e $L_2$, a linguagem $L_1\cup L_2$ é regular.

Prova

Uma vez que $L_1$ e $L_2$ são regulares, existem AFNs $N_1,N_2$ que reconhecem $L_1$ e $L_2$.

Seja

$N_1=(Q_1,\mathrm{\Sigma },T_1,q_1,A_1)$

$N_2=(Q_2,\mathrm{\Sigma },T_2,q_2,A_2)$

Vamos construir

$N=(Q,\mathrm{\Sigma },T,q_0,A_1\cup A_2)$

onde

$Q=Q_1\cup Q_2\cup \{q_0\}$

$T(q,x)=\{\begin{array}{ccc}{T}_1(q,x)& \text{se}& q\in Q_1\\ T_2(q,x)& \text{se}& q\in Q_2\\ \{q_1,q_2\}& \text{se}& q=q_{0}ex=ϵ\\ \mathrm{\varnothing }& \text{se}& q=q_{0}ex\ne ϵ\end{array}$

Em seguida, vamos usar $p\stackrel{x,T}{\to }q$ para denotar $q\in E(T(p,x))$

Seja $w$ uma string de $L_1\cup L_2$. Sem perda de generalidade, assumimos $w\in L_1$.

Seja $w=x_1{x}_2\cdots x_m$ onde $m\ge 0,x_i\in \mathrm{\Sigma }$

Uma vez que $N_1$ aceita $x_1{x}_2\cdots x_m$, existem $r_0,r_1,\cdots r_m\in Q_1$ tais que

$q_1\stackrel{ϵ,T_1}{\to }{r}_0\stackrel{x_1,T_1}{\to }{r}_1\stackrel{x_2,T_1}{\to }{r}_2\cdots r_{m-1}\stackrel{x_m,T_1}{\to }{r}_m,r_m\in A_1$

Desde que $T_1(q,x)=T(q,x)\mathrm{\forall }q\in Q_1\mathrm{\forall }x\in \mathrm{\Sigma }$

$r_0\in E(T_1(q_1,ϵ))\Rightarrow r_0\in E(T(q_1,ϵ))$

$r_1\in E(T_1(r_0,x_1))\Rightarrow r_1\in E(T(r_0,x_1))$

$⋮$

$r_m\in E(T_1(r_{m-1},x_m))\Rightarrow r_m\in E(T(r_{m-1},x_m))$

Nós podemos, portanto, substituir $T$ por $T_1$ e rescrever o caminho acima como:

$q_1\stackrel{ϵ,T}{\to }{r}_0\stackrel{x_1,T}{\to }{r}_1\stackrel{x_2,T}{\to }{r}_2\cdots r_{m-1}\stackrel{x_m,T}{\to }{r}_m,r_m\in A_1\cup A_2,r_0,r_1,\cdots r_m\in Q$

Além disso,

$\begin{array}{ccc}T(q_0,ϵ)=\{q_1,q_2\}& \Rightarrow & q_1\in T(q_0,ϵ)\\ \\ & \Rightarrow & q_1\in E(T(q_0,ϵ))\\ \\ & \Rightarrow & q_0\stackrel{ϵ,T}{\to }{q}_1\end{array}$

e

$q_0\stackrel{ϵ,T}{\to }{q}_1\stackrel{ϵ,T}{\to }{r}_0\Rightarrow q_0\stackrel{ϵ,T}{\to }{r}_0$

O caminho acima pode ser reescrito como:

$q_0\stackrel{ϵ,T}{\to }{r}_0\stackrel{x_1,T}{\to }{r}_1\stackrel{x_2,T}{\to }{r}_2\cdots r_{m-1}\stackrel{x_m,T}{\to }{r}_m,r_m\in A_1\cup A_2,r_0,r_1,\cdots r_m\in Q$

Portanto, $N$ aceita $x_1{x}_2\cdots x_m$ e a prova está concluída.

Nota: A ideia extraída desta prova matemática para construção de uma máquina para reconhecer $L_1\cup L_2$ é criar um estado inicial e conectá-lo aos estados iniciais de $L_1$ e $L_2$ usando transições vazias ($ϵ$).

Referências

• Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (Teorema 1.22, seção 1.2, pg. 59.)