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.

Para quaisquer linguagens regulares ${\displaystyle L_{1}}$ e ${\displaystyle L_{2}}$, a linguagem ${\displaystyle L_{1}\cup L_{2}}$ é regular.

Prova

Uma vez que ${\displaystyle L_{1}}$ e ${\displaystyle L_{2}}$ são regulares, existem AFNs ${\displaystyle N_{1},\ N_{2}}$ que reconhecem ${\displaystyle L_{1}}$ e ${\displaystyle L_{2}}$.

Seja

${\displaystyle N_{1}=(Q_{1},\ \Sigma ,\ T_{1},\ q_{1},\ A_{1})}$

${\displaystyle N_{2}=(Q_{2},\ \Sigma ,\ T_{2},\ q_{2},\ A_{2})}$

Vamos construir

${\displaystyle N=(Q,\ \Sigma ,\ T,\ q_{0},\ A_{1}\cup A_{2})}$

onde

${\displaystyle Q=Q_{1}\cup Q_{2}\cup \{q_{0}\}}$

${\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 ${\displaystyle p{\stackrel {x,T}{\rightarrow }}q}$ para denotar ${\displaystyle q\in E(T(p,x))}$

Seja ${\displaystyle w}$ uma string de ${\displaystyle L_{1}\cup L_{2}}$. Sem perda de generalidade, assumimos ${\displaystyle w\in L_{1}}$.

Seja ${\displaystyle w=x_{1}x_{2}\cdots x_{m}}$ onde ${\displaystyle m\geq 0,x_{i}\in \Sigma }$

Uma vez que ${\displaystyle N_{1}}$ aceita ${\displaystyle x_{1}x_{2}\cdots x_{m}}$, existem ${\displaystyle r_{0},r_{1},\cdots r_{m}\in Q_{1}}$ tais que

${\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 ${\displaystyle T_{1}(q,x)=T(q,x)\ \forall q\in Q_{1}\forall x\in \Sigma }$

${\displaystyle r_{0}\in E(T_{1}(q_{1},\epsilon ))\Rightarrow r_{0}\in E(T(q_{1},\epsilon ))}$

${\displaystyle r_{1}\in E(T_{1}(r_{0},x_{1}))\Rightarrow r_{1}\in E(T(r_{0},x_{1}))}$

${\displaystyle \vdots }$

${\displaystyle 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 ${\displaystyle T}$ por ${\displaystyle T_{1}}$ e rescrever o caminho acima como:

${\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}$

Além disso,

${\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

${\displaystyle q_{0}{\stackrel {\epsilon ,T}{\rightarrow }}q_{1}{\stackrel {\epsilon ,T}{\rightarrow }}r_{0}\Rightarrow q_{0}{\stackrel {\epsilon ,T}{\rightarrow }}r_{0}}$

O caminho acima pode ser reescrito como:

${\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}$

Portanto, ${\displaystyle N}$ aceita ${\displaystyle 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 ${\displaystyle L_{1}\cup L_{2}}$ é criar um estado inicial e conectá-lo aos estados iniciais de ${\displaystyle L_{1}}$ e ${\displaystyle L_{2}}$ usando transições vazias (${\displaystyle \epsilon }$).

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