DFA Complement - Automata Theory

What is DFA Complement?

If (Q, ∑, δ,q0, F) is considered as a DFA that accepts a language L, then the other related components of the DFA can be derived by swapping its accepting states with its non-accepting states and vice versa.

Let’s take following example and explained this below −

dfa_accepting_language_l

This DFA accepts the language

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

over the alphabet

∑ = {a, b}

So, RE =a+.

You can swap its accepting states with its non-accepting states and vice versa and will get the following −

dfa_accepting_complement_language_l

This DFA accepts the language

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

over the alphabet

∑ = {a, b}

Note − If we want to complement an NFA, we have to first convert it to DFA and then have to swap states as in the previous method.

Automata Theory Related Tutorials

Automata Theory Related Practice Tests

All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

Automata Theory Topics