Show how to define the following languages over = {0, 1} 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 operation. Below or always means inclusive or. (a) All strings that have both 000 and 111 as a substring. (b) All strings that have 0000 or 1111 as a substring. (c) All strings that both begin and end with 0110. (Note that the prefix 0110 and the suffix 0110 may overlap.) (d) All strings that do not have 111 as a substring. (e) All strings that have even length and, at the same time, have 010 as a substring.

3. (5 marks) Show how to define the following languages over = {0,1} using only e, the alphabet symbols 0 and 1, and the operations of union, concatenation, and closure. Note: Your answer cannot use the intersection or complementation operation. Below "or" always means "inclusive or. (a) All strings that have both 000 and 111 as a substring. (b) All strings that have 0000 or 1111 as a substring. (c) All strings that both begin and end with 0110. (Note that the prefix 0110 and the suffix 0110 may overlap.) (d) All strings that do not have 111 as a substring. (e) All strings that have even length and, at the same time, have 010 as a substring