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.Michael Sipser - Introduction to the Theory of Computation.
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.John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introdução à Teoria de Autômatos, Linguagens e Computação (2ª Edição).
Seja
Vamos construir
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 ,
Categoria:Linguagens formais Categoria:Teoria dos autômatos