A operação de união consiste em

 

União: A U B = {x | x ∈ A ou x ∈ B}

 

 

 

 

 

 

 

 

 

Suponha que as linguagens regulares A e B possuam o conjunto de cadeias como descrito abaixo. E que a partir de A e B queremos construir uma linguagem mais complexa C.

 

A = {a, b, c , d}

B = {e, f, g, h}

C = {a, b, c, d, e, f, g, h}

 

Temos duas maneiras de enxergar este problema: uma didática e uma maneira real (o que acontece de fato).

 

Forma didática:

A partir do conjunto A e B podemos utilizar a operação de união para que possamos gerar um conjunto da linguagem C

Então fazendo a operação união entre os elementos do conjunto A com os do conjunto B podemos perceber que o conjunto C se forma a partir da junção entre os elementos do conjunto A e os elementos do conjunto B.

Note que não há necessidade de repetir os elementos na formação do conjunto C quando eles estão presentes nos dois conjuntos A e B.

 

 

 

 

 

 

 

 

 

 

Forma real :

O que ocorre é que teremos dois conjuntos A e B, e ainda queremos chegar à um outro conjunto C, que seguem as mesmas cadeias citadas no começo. 

Assim, teremos que analisar o conjunto que queremos chegar e optar pela operação que conseguirá nos levar à este resultado. 

Como no exemplo, podemos perceber que o conjunto C tem uma padrão existente de unir os elementos pertencentes ao conjunto A e B, então a melhor operação a ser usada seria a de união.

 

 

 

 

 

 

Explicaremos agora como funciona passo a passo a resolução da operação e a montagem do autômato finito que representa a linguagem final, mais complexa,  que queremos construir:

 

A partir de duas linguagens regulares L1 e L2, para garantir que L1 U L2 seja válido e gere uma linguagem regular pode-se utilizar a prova por automatos finitos. Sendo assim, deve-se gerar dois autômatos finitos não determinísticos (AFNDs), uma para L1 e um para L2, chamados de M1 e M2, respectivamente. Cada um dos AFNDs deverá ser representado por Q (quais estados possui), Σ (alfabeto que é composto), δ (a função), q (o estado inicial), F (estados terminais).

 

Temos as linguagens abaixo L1 e L2:

 

L1:

 

 

 

                                                                                                                       M1 = ( {e0, e1, e2, e3}, {0,1}, δ, e0, {e3} ) 

 

 

 

 

 

 

 

L2

 

 

 

                                                                M2 = ( {t0 t1, t2}, {0,1}, δ, t0, {t2} )

 

 

 

 

 

 

Para gerar a união dos dois autômatos gerados, é necessário seguir o seguinte algoritmo:

1) Temos que os autômatos são representados por:

  M1 = (Q1, Σ1, δ1, q1, F1)   

  M2 = (Q2, Σ2, δ2, q2, F2);    

2) Unir os dois alfabetos (Σ1 U Σ2);    

3) Criar um estado inicial chamado de So;  

4) Copiar M1 e M2 sem identificar os estados terminais e iniciais;

5) Realiza a ligação de So com os estados que recebiam setas dos iniciais de L1 e L2 (So -> estado) mantendo o caractere;

6) Se ʎ pertencer a L1 ou L2:   

  * os estados finais serão os já exitentes nos automatos M1 e M2 acrescentando o estado So criado;    

7) Se ʎ NÃO pertencer a L1 ou L2:   

  * os estados finais serão os já existentes em M1 e M2;   

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

M3 = ({s0, e0, e1, e2, e3, t0, t1, t2}, {0,1}, δ3, s0, {e3, t2})

 

 

 

 

Referência: Lemma 3.1 , Hopcroft, JOHN E. , Ullman, Jeffrey D. - Formal Languages and their Relation to Automata - 1969 - Cap.3 pag. 35