Complemento de DFA

Si (Q, ∑, δ, q 0 , F) es un DFA que acepta un lenguaje L, entonces el complemento del DFA se puede obtener intercambiando sus estados de aceptación con sus estados de no aceptación y viceversa.

Tomaremos un ejemplo y lo elaboraremos a continuación:

Este DFA acepta el idioma

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

sobre el alfabeto

∑ = {a, b}

Entonces, RE = a + .

Ahora intercambiaremos sus estados de aceptación con sus estados de no aceptación y viceversa y obtendremos lo siguiente:

Este DFA acepta el idioma

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

sobre el alfabeto

∑ = {a, b}

Note - Si queremos complementar un NFA, primero tenemos que convertirlo a DFA y luego tenemos que intercambiar estados como en el método anterior.