Если (Q, ∑, δ, q 0 , F) — DFA, который принимает язык L, то дополнение DFA может быть получено путем замены его принимающих состояний на неприемлемые и наоборот.
Мы возьмем пример и уточним это ниже —
Это DFA принимает язык
L = {a, aa, aaa, ………….}
по алфавиту
∑ = {a, b}
Итак, RE = + .
Теперь мы поменяем его принимающие состояния на непринятые и наоборот и получим следующее:
Это DFA принимает язык
Ľ = {ε, b, ab, bb, ba, ……………}
по алфавиту
∑ = {a, b}
Примечание. Если мы хотим дополнить NFA, мы должны сначала преобразовать его в DFA, а затем поменять местами, как в предыдущем методе.