A operação de fecho consiste em

 

Fechamento: A*

 

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

 

A = {ab, cd}

C = {ababab, ab, abab, abdc, cdcd, cd...}

 

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 podemos utilizar a operação de fecho para que possamos gerar um conjunto da linguagem C

Então temos que o fecho de A é quando temos os elementos do conjunto sendo recombinados para gerar a linguagem mais complexa C.

Então temos a combinação entre os vários elementos do conjunto A, podendo também ser uma das combinação a repetição de um mesmo elemento (zero uma ou mais vezes), combinação de dois elemento ou então trocar a ordem dos elementos, ou seja, abcd, abab, cdab respectivamente.

Perceba que podemos trocar a ordem dos elementos na formação da cadeia, como no caso podemos ter abcd, como também cdab, mas temos que tomar cuidado pois não podemos trocar a ordem do elemento, como por exemplo mudar o elemento ab para ba.

 

 

 

 

 

 

 

 

 

 

Forma real:

O que ocorre é que teremos dois conjuntos A, 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 qua existem várias combinações entre os elementos do conjunto, repetindo o mesmo elemento ou não zero ou mais vezes, e isso lembra a ideia de fecho, sendo então o fecho a melhor operação para construir essa linguagem

 

 

 

 

 

 

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:

 

 

Para gerar o fechamento da linguagem regular L1 e garantir que está também seja regular pode-se utilizar a prova por autômatos finitos. Sendo assim, deve-se gerar um automato finito não determinístico (AFND) para L1, chamado de M1. O AFND 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:

 

 

 

 

 

 

 

 

 

 

 

L2:

 

 

 

 

 

 

 

 

Para gerar o fechamento do automato gerado, é necessário seguir o seguinte algoritmo:

1) Temos que o automato M1 é representado por:

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

2) Manter o alfabeto Σ1;

3) Copiar M1;

4) Criar um novo estado q'0;

5) Adicionar q'0 aos estados terminais;

6) Definir q'0 como o estado inicial;

7) Qualquer outro estado mantem as transições, exceto q'0;

8) Caso um estado leve a um estado terminal, além de manter a transição, adicionar uma seta para o estado inicial de L1, mantendo o caractere que usava para ligar com o estado terminal;

9) Ligação de q'0:

  * realizar ligação de q'0 com os estados que recebiam setas do estado inicial de L1, mantendo o caractere;

  * além disso, se o estado inicial de L1 levar a um estado terminal, realizar a ligação de q'0 com o inicial de L1.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

M3 = ({e0, e1, e2, e3, q'0}, {0, 1}, δ3, q'0, {e3})

 

 

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