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
e
, a linguagem
é regular.[1]
Prova
Uma vez que
e
são regulares, existem AFNs
que reconhecem
e
, respectivamente.
A ideia é adicionar transições
partindo dos estados de aceitação de
para o estado inicial de
, significando que ele encontrou uma parte inicial da entrada que constitui uma cadeia em
. Os estados de aceitação de
deixam de ser estados de aceitação, e o estado inicial de
deixa de ser estado inicial, passando a serem estados do autômato
.
Por conseguinte,
aceita uma cadeia de entrada quando podemos dividi-la em duas partes, sendo a primeira aceita por
e a segunda aceita por
. Portanto,
"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})}](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_{1},\ A_{2})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/713db5377517ee5d90fa8b46673ad11de1291753)
tal que
1.
Os estados de
são todos os estados de
e
.
2. O estado inicial
de
é o estado inicial de
.
3. Os estados de aceitação
de
são os estados de aceitação de
.
4. Defina T de modo que para qualquer
e qualquer
,
![{\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.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d0d27eb0df3f7241349b37db6a8692fc85fbeb4)
Referências
- ↑ Michael Sipser - Introduction to the Theory of Computation.
- ↑ John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introdução à Teoria de Autômatos, Linguagens e Computação (2ª Edição).