Complemento DFA

Se (Q, ∑, δ, q ₀ , F) è un DFA che accetta una lingua L, allora il complemento del DFA può essere ottenuto scambiando i suoi stati di accettazione con i suoi stati di non accettazione e viceversa.

Faremo un esempio e lo elaboreremo di seguito:

Questo DFA accetta la lingua

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

sopra l'alfabeto

∑ = {a, b}

Quindi, RE = a ⁺ .

Ora cambieremo i suoi stati di accettazione con i suoi stati di non accettazione e viceversa e otterremo quanto segue:

Questo DFA accetta la lingua

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

sopra l'alfabeto

∑ = {a, b}

Note - Se vogliamo integrare un NFA, dobbiamo prima convertirlo in DFA e poi scambiare gli stati come nel metodo precedente.