Concatenação de duas linguagens regulares

Predefinição:Sem notas 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 $\epsilon$ 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,\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_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 {\mathrm{\Sigma }}_{\epsilon }$,

$T(q,x)=\{\begin{array}{ccc}{T}_1(q,x)& & q\in Q_{1}eq\notin A_1\\ T_1(q,x)& & q\in A_{1}ex\ne \epsilon \\ T_1(q,x)\cup \left\{q_2\right\}& & q\in A_{1}ex=\epsilon \\ T_2(q,x)& & q\in Q_2\end{array}$