União de duas linguagens regulares

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na teoria das linguagens formais, e em particular na teoria dos autômatos finitos não determinísticos, é conhecido que a união de duas linguagens regulares é uma linguagem regular. Este artigo fornece uma prova desta afirmação.

Teorema[editar | editar código-fonte]

Para quaisquer linguagens regulares e , a linguagem é regular.

Prova

Uma vez que e são regulares, existem AFNs que reconhecem e .

Seja

Vamos construir

onde

Em seguida, vamos usar para denotar

Seja uma string de . Sem perda de generalidade, assumimos .

Seja onde

Uma vez que aceita , existem tais que

Desde que


Nós podemos, portanto, substituir por e rescrever o caminho acima como:



Além disso,

e


O caminho acima pode ser reescrito como:



Portanto, aceita e a prova está concluída.


Nota: A ideia extraída desta prova matemática para construção de uma máquina para reconhecer é criar um estado inicial e conectá-lo aos estados iniciais de e usando transições vazias ().

Referências[editar | editar código-fonte]

  • Michael Sipser, Introduction to the Theory of Computation ISBN 0-534-94728-X. (Teorema 1.22, seção 1.2, pg. 59.)