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
e
, a linguagem
é regular.
Prova
Uma vez que
e
são regulares, existem AFNs
que reconhecem
e
.
Seja
![{\displaystyle N_{1}=(Q_{1},\ \Sigma ,\ T_{1},\ q_{1},\ A_{1})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/60b0c3dc0811c3219a360c95171f5493c7621098)
![{\displaystyle N_{2}=(Q_{2},\ \Sigma ,\ T_{2},\ q_{2},\ A_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0285e1312b087252001838604dfd417d2dd987a6)
Vamos construir
![{\displaystyle N=(Q,\ \Sigma ,\ T,\ q_{0},\ A_{1}\cup A_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/636b80cedc10bb240d7e7e5ed6ab3a75aee793da)
onde
![{\displaystyle Q=Q_{1}\cup Q_{2}\cup \{q_{0}\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c85d7fbfd3a1fa45cd5794911510abe5400d863a)
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/72436797cc9a6b3bf344bafa5573d6f82de12084)
Em seguida, vamos usar
para denotar
Seja
uma string de
. Sem perda de generalidade, assumimos
.
Seja
onde
Uma vez que
aceita
, existem
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a48d07f432906c662102af49ab1ecf40c7d888fe)
Desde que
![{\displaystyle r_{0}\in E(T_{1}(q_{1},\epsilon ))\Rightarrow r_{0}\in E(T(q_{1},\epsilon ))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/90afe6e1914ba65c7cf163318bd1afd8ba0488d7)
![{\displaystyle r_{1}\in E(T_{1}(r_{0},x_{1}))\Rightarrow r_{1}\in E(T(r_{0},x_{1}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/caad9eb0e90dbb80a894cc79d2d841cb0574edce)
![{\displaystyle \vdots }](https://wikimedia.org/api/rest_v1/media/math/render/svg/f8039d9feb6596ae092e5305108722975060c083)
![{\displaystyle r_{m}\in E(T_{1}(r_{m-1},x_{m}))\Rightarrow r_{m}\in E(T(r_{m-1},x_{m}))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e1f96b9bfa788c19ab9318c5c1ed549bb4d3ca7c)
Nós podemos, portanto, substituir
por
e rescrever o caminho acima como:
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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e54723303e02669dbc787a58136341689b548b5c)
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}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa1ee6b8721b9cfb6252c7f5f2b33e6f81e7e022)
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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4ee90c04d4b36763882c311bbc2c5bda2d8750fe)
Portanto,
aceita
e a prova está concluída.
Nota: A ideia extraída desta prova matemática para construção de uma máquina para reconhecer
é criar um estado inicial e conectá-lo aos estados iniciais de
e
usando transições vazias (
).
- Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (Teorema 1.22, seção 1.2, pg. 59.)