DFA Tamamlayıcı

(Q, ∑, δ, q ₀ , F) bir L dilini kabul eden bir DFA ise, o zaman DFA'nın tamamlayıcısı, kabul etme durumlarını kabul etmeme durumlarıyla değiştirerek elde edilebilir ve bunun tersi de geçerlidir.

Bir örnek alacağız ve bunu aşağıda detaylandıracağız -

Bu DFA, dili kabul ediyor

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

alfabenin üzerinde

∑ = {a, b}

Yani RE = a ⁺ .

Şimdi kabul eden durumlarını kabul etmeyen durumlarıyla değiştireceğiz ve bunun tersi de geçerli olacak ve aşağıdakileri alacağız -

Bu DFA, dili kabul ediyor

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

alfabenin üzerinde

∑ = {a, b}

Note - Bir NFA'yı tamamlamak istiyorsak, önce onu DFA'ya dönüştürmeli ve ardından önceki yöntemde olduğu gibi durumları değiştirmeliyiz.