A operação de diferença consiste em

 

Diferença: A - B = {x | x ∈ A e 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 = {a, b, e, f, g, h}

C = {c, d}

 

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

Então fazendo a diferença, analisaremos o conjunto antes do sinal negativo, que seria o A, ele que será a base do conjunto final C e então retiramos deste conjunto A os elementos que estão em B. No caso os elementos de B que estão em A é a e b, então o conjunto final seria o conjunto A menos os elementos a e b 

Perceba que a diferença A - B não resulta em um mesmo conjunto que B - A

 

 

 

 

 

 

 

 

 

 

 

Forma real:

O que ocorre é que teremos dois conjuntos A e B, e ainda queremos chegar à um outro conjunto C, que seguem oas 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 que u conjunto final C é a diferença entre os conjuntos, então analisamos melhor para saber qual dos dois conjuntos (A ou B) é a base para podermos fazer a diferença corretamente. Se a base for A, a diferença é A - B, e se a base for B, a diferença é B - A. Então a melhor operação a ser usada seria a da diferença.

 

 

 

 

 

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. Para isso, é necessário utlizar os conceitos de intersecção e complemento, sendo assim, a diferença de duas linguagens regulares pode ser representada por: