Complemento DFA
Se (Q, ∑, δ, q 0 , 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.