Problem 1: Write a regular expression for the language L, over alphabet {0, 1, 2}, such that every 0 that is not the last (rightmost) symbol is immediately followed by a 1, and every 1 that is not the last symbol is immediately followed by a 0. By "immediately followed" we mean "with no intervening symbols. Thus, 010 is in L, but 001 is not, because the first 0 is not immediately followed by 1. 021 is not in L for the same reason.

Problem 2: Describe an algorithm that converts an NFA A into a DFA whose language is the complement of L(A). The complement should be taken with respect to the alphabet of A. Give an informal argument for why your construction works. You need not give a formal proof.

Problem 3: Give a decision algorithm that tells whether a DFA A has the following property: if string w is in L(A), then so is the string ww. For example, a DFA that accepts the empty language has the property (vacuously). If L(A) is 0*, then it also has the property. But if L(A) is all strings of 0's and 1's without two consecutive 1's, then A does not have the property. In proof. note that w = 101 is in the language, but ww = 101101 is not. You should give the algorithm and an intuitive argument why it works, but again, no formal proof is needed. A Hint is available and may be consulted at any time.