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.

Para quaisquer linguagens regulares ${\displaystyle L_{1}}$ e ${\displaystyle L_{2}}$, a linguagem ${\displaystyle L_{1}\circ L_{2}}$ é regular.^[1]

Prova

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

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

Por conseguinte, ${\displaystyle N}$ aceita uma cadeia de entrada quando podemos dividi-la em duas partes, sendo a primeira aceita por ${\displaystyle N_{1}}$ e a segunda aceita por ${\displaystyle N_{2}}$. Portanto, ${\displaystyle N}$ "adivinha" não-deterministicamente onde fazer a divisão necessária.^[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_{1},\ A_{2})}$

tal que

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

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

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

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

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

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

Referências