Учебники

DFA Дополнение

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

Мы возьмем пример и уточним это ниже –

DFA Accepting Language L

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

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

по алфавиту

∑ = {a, b}

Итак, RE = + .

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

DFA Accepting Complement Language L

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

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

по алфавиту

∑ = {a, b}

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