DFA補数

（Q、∑、δ、q ₀、F）が言語Lを受け入れるDFAである場合、DFAの補集合は、受け入れ状態を非受け入れ状態と交換することによって取得できます。その逆も同様です。

例を挙げて、これを以下で詳しく説明します-

このDFAは言語を受け入れます

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

アルファベットの上

∑ = {a、b}

したがって、RE = a ⁺。

ここで、受け入れ状態を非受け入れ状態と交換し、その逆も行います。次のようになります。

このDFAは言語を受け入れます

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

アルファベットの上

∑ = {a、b}

Note − NFAを補完する場合は、最初にそれをDFAに変換してから、前の方法と同様に状態を交換する必要があります。