Concatenaçã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 concatenaçã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}\circ L_{2}$ é regular.

Prova

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

A ideia é adicionar transições $\varepsilon$ partindo dos estados de aceitação de $N_{1}$ para o estado inicial de $N_{2}$, significando que ele encontrou uma parte inicial da entrada que constitui uma cadeia em $L_{1}$. Os estados de aceitação de $N_{1}$ deixam de ser estados de aceitação, e o estado inicial de $N_{2}$ deixa de ser estado inicial, passando a serem estados do autômato $N$.

Por conseguinte, $N$ aceita uma cadeia de entrada quando podemos dividi-la em duas partes, sendo a primeira aceita por $N_{1}$ e a segunda aceita por $N_{2}$. Portanto, $N$ "adivinha" não-deterministicamente onde fazer a divisão necessária.

Seja

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

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

Vamos construir

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

tal que

1. $Q=Q_{1}\cup Q_{2}$

Os estados de $N$ são todos os estados de $N_{1}$ e $N_{2}$.

2. O estado inicial $q_{1}$ de $N$ é o estado inicial de $N_{1}$.

3. Os estados de aceitação $A_{2}$ de $N$ são os estados de aceitação de $N_{2}$.

4. Defina T de modo que para qualquer $q\in Q$ e qualquer $x\in \Sigma _{\varepsilon }$,

$T(q,x)=\left\{{\begin{array}{lll}T_{1}(q,x)&&q\in Q_{1}\ e\ q\notin A_{1}\\T_{1}(q,x)&&q\in A_{1}\ e\ x\neq \varepsilon \\T_{1}(q,x)\cup \left\{q_{2}\right\}&&q\in A_{1}\ e\ x=\varepsilon \\T_{2}(q,x)&&q\in Q_{2}\\\end{array}}\right.$