Operação fechada: Complemento

A operação de complemento consiste em

 

Complemento: Ā = {x | x ∉ A}  ou  U - A = {x | x ∉ A}

 

 

 

 

 

 

 

 

 

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}

 

C = U (conjunto inverso)

 

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 complemento para que possamos gerar um conjunto da linguagem C

Então temos que o complemento de A é tudo o que falta em A para completar o conjunto relativo ao complemento, ou seja, neste caso seria o conjunto universo C. 

Então vemos que o que falta em A para completar o universo, seria tudo (o universo) menos o A. Supondo que nosso conjunto universo seja D = {a, b, c, d, e} e mantendo o mesmo conjunto A citado acima temos que o complemento de A em relação ao universo D seria

D - A por definição:

 

 

 

 

 

 

 

 

 

 

 

 

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 que estamos querendo construir é o que completa A em relação ao universo, que seria exatamente os elementos do universo menos os elementos de A.

 

 

 

 

 

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 complemento 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 autômato 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 complemento do automato gerado, é necessário seguir o seguinte algoritmo:

1) Temos que o automato M1 é representado por:

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

2) Criar um novo alfabeto que contenha o alfabeto Σ1 ou manter o alfabeto Σ1;

3) Criar um estado d e definir como final;

4) Manter o estado inicial;

5) Tornar TODOS os estados NÃO terminais em estados terminais e os terminais em estado de transição comuns (menos o estado d);

6) Manter as transições iniciais;

7) Fazer um loop de d para d com todos os caracteres do alfabeto;

8) Todos os estados que possuem ausência de algum caractere devem se ligar a d (estado -> d), incluindo os caracteres em questão nessa transição.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

M3 = ({t0, t1, t2, d}, {0, 1}, δ3, t0, {t1, d})

 

 

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