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 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


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 ,


Referências

  1. Michael Sipser - Introduction to the Theory of Computation.
  2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman - Introdução à Teoria de Autômatos, Linguagens e Computação (2ª Edição).