Complément DFA

Si (Q, ∑, δ, q ₀ , F) est un DFA qui accepte une langue L, alors le complément du DFA peut être obtenu en échangeant ses états acceptants avec ses états non acceptants et vice versa.

Nous prendrons un exemple et développerons ceci ci-dessous -

Ce DFA accepte la langue

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

sur l'alphabet

∑ = {a, b}

Donc, RE = a ⁺ .

Maintenant, nous allons permuter ses états acceptants avec ses états non acceptants et vice versa et obtiendrons ce qui suit -

Ce DFA accepte la langue

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

sur l'alphabet

∑ = {a, b}

Note - Si nous voulons compléter un NFA, nous devons d'abord le convertir en DFA, puis permuter les états comme dans la méthode précédente.