A operação de concatenação consiste em

 

Concatenação: A º B = {xy | x ∈ A e y ∈ 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 = {ae, af, ag, ah, be, bf, bg, bh, ce, cf, cg, ch, de, df, dg, dh}

 

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 concatenação para que possamos gerar um conjunto da linguagem C

Então fazendo a concatenação entre os elementos do conjunto A com os do conjunto B, obteremos assim o resultado, que seria o conjunto C.

Perceba que a concatenação ocorre entre um elemento do conjunto A com um elemento do conjunto B, pois não existe concatenação entre os elementos do conjunto A entre si e nem entre os elementos do conjunto B entre si, como na figura abaixo:

 

 

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 concatenar elementos, então a melhor operação a ser usada seria a de concatenaçã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 . 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 concatenação dos dois automatos gerados, é necessário seguir o seguinte algoritmo:

1) Temos que os automatos são representados por:

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

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

2) Unir os alfabetos Σ1 e Σ2;

3) Copiar os estados Q1 e Q2 e manter as transições de L1 e L2;;

4) O estado inicial da concatenação é definido como o estado inicial de L1 (q1);

5) Realizar as ligações dos estados terminais de L1 com os estados que recebiam setas do inicial de L2, mantendo o caractere;

6) Se ʎ pertencer a L2:

     * manter todos os estados terminais de L1 e L2;

7) Se ʎ NÃO pertencer a L2:

     * manter apenas os estados terminais de L2.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

 

 

 

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