Operações sobre linguagens

Reunião

Reunião da linguagem L1 e da linguagem L2.

• L1 U L2

Se definidas no alfabeto A = {a, b}.

O resultado de L1 U L2 = L será:

Intercepção

Se definidas no alfabeto A = {a, b}.

O resultado da Intercepção será:

Diferença

Se definidas no alfabeto A = {a, b}.

O resultado de L1 - L2 = L será:

Complementação

Se definida no alfabeto A = {a, b}.

O resultado ~L será:

Concatenação

Se definidas no alfabeto A = {a, b}.

O resultado de L1 . L2 = L será:

Potenciação

Se definida no alfabeto A = {a, b}.

O resultado de (L1)^2 = L será:

Fecho de Kleene

Se definida no alfabeto A = {a, b}.

O fecho de Kleene será:

Notas adicionais

Note que nas operações binárias sobre conjuntos não é requerido que as duas linguagens estejam definidos sobre o mesmo alfabeto.

Assim se tivermos duas linguagens L1 e L2 definidas respectivamente sobre os alfabetos A1 e A2, então o alfabeto resultante da aplicação duma qualquer operação binária sobre as linguagens é a união de A1 e A2.