Automata

Complementation of DFAs

We will discuss this property using one example:




So as you see in the above picture, we have taken one DFA (containing 'a') and complementation is "not containing 'a'"
L1 = {a, aa, ba, baa, aaa, ...}
After taking complementation
L = {ε, b, bb, bbb, bbbb, ....}

We simply make start state as final state and vice versa Note: clearly the language is infinite
You can also take some examples from the previous exercises for practice.



Quantitative Aptitude
Reasoning
Programming
Interview