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.