Uzupełnienie DFA
Jeśli (Q, ∑, δ, q 0 , F) jest DFA akceptującym język L, to uzupełnienie DFA można uzyskać, zamieniając jego stany akceptujące na stany nieakceptujące i odwrotnie.
Weźmy przykład i omówimy to poniżej -
Ten DFA akceptuje język
L = {a, aa, aaa, .............}
nad alfabetem
∑ = {a, b}
Więc RE = a + .
Teraz zamienimy jego stany akceptujące na stany nieakceptujące i na odwrót i otrzymamy:
Ten DFA akceptuje język
Ľ = {ε, b, ab, bb, ba, ...............}
nad alfabetem
∑ = {a, b}
Note - Jeśli chcemy uzupełnić NFA, musimy najpierw przekonwertować go na DFA, a następnie zamienić stany, jak w poprzedniej metodzie.