Complemento DFA

Se (Q, ∑, δ, q ₀ , F) for um DFA que aceita uma linguagem L, então o complemento do DFA pode ser obtido trocando seus estados de aceitação por seus estados de não aceitação e vice-versa.

Vamos dar um exemplo e elaborá-lo abaixo -

Este DFA aceita o idioma

L = {a, aa, aaa, .............}

sobre o alfabeto

∑ = {a, b}

Portanto, RE = a ⁺ .

Agora vamos trocar seus estados de aceitação por seus estados de não aceitação e vice-versa e obteremos o seguinte

Este DFA aceita o idioma

Ľ = {ε, b, ab, bb, ba, ...............}

sobre o alfabeto

∑ = {a, b}

Note - Se quisermos complementar um NFA, primeiro temos que convertê-lo para DFA e depois trocar os estados como no método anterior.