Дополнение DFA

Если (Q, ∑, δ, q ₀ , F) является DFA, который принимает язык L, то дополнение DFA может быть получено путем замены его принимающих состояний на его неприняющие состояния и наоборот.

Мы возьмем пример и подробно рассмотрим это ниже -

Этот DFA принимает язык

L = {а, аа, ааа, .............}

по алфавиту

∑ = {a, b}

Итак, RE = a ⁺ .

Теперь мы поменяем его принимающие состояния на непринятие и наоборот и получим следующее:

Этот DFA принимает язык

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

по алфавиту

∑ = {a, b}

Note - Если мы хотим дополнить NFA, мы должны сначала преобразовать его в DFA, а затем поменять местами состояния, как в предыдущем методе.