For = {a, b} the complement of a set A is ~A = {x * | x A}. So the complement of A is the set of all strings in * that are not in A.

A)

The language L = {w | w does not contain either of the substrings ab or ba} is the complement of a simpler language L. Think about what strings would be in L and then construct a DFA for L. Last, use that state diagram for L to give a DFA for L.

B)

Let L = {w | w contains the substring abba}. Prove that ~L (the complement of L) is a regular language. You need to use the definition for regular language in your proof.