Show how to define the following languages over = {a, b} using only , the alphabet symbols 0 and 1, and the operations of union, concatenation, and closure. Note: Your answer cannot use the intersection or complementation operations.

(a) All strings that have 0000 as a prefix or 1111 as a suffix.

(b) All strings that both begin and end with 101. (Note that the prefix 101 and the suffix 101 may overlap.)

(c) All strings that have both 000 as a prefix and 001 as a substring. Note that the prefix and the substring may overlap.

(d) All strings that have odd length and, at the same time, have 0011 as a substring.

(e) All strings w satisfying condition (i) or condition (ii):

i. w has at most three occurrences of 0; ii. w has at most three occurrences of 1.