Complements

For = {a, b} the complement of a set A is ~A = {x (not an element of) * | x (is an element of) 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. Hint, see problem 3. a..

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.