1. Given an alphabet , are and languages? Explain why or why not.

2. Let = {0,1}. Let L1 = {w + | w has an even number of 1s}, L2 = {w | w starts with 1 and end in all 0s}. Using set builder notation describe L1L2.

3. Let = {0,1}. Dene the function, F : Languages, as follows:

(a) F() = and F(x) = {x}x .

(b) F(w1 w2) = F(w1)F(w2).

(c) F(w1 w2) = F(w1)F(w2).

(d) F(w 1) = F(w1).

Use (a) through (d) to prove or disprove that F((((01)0)1)) = {0,1}{1}

4. Let = {0,1}. Let L = {w | |w|0 6= |w|1}. Prove or disprove that L = .

5. Let w = ab for = {a,b}. What are the following string:

(a) w0?

(b) w4?

(c) w1?

(d) w2ww2?

(e) w0w0w2w0?

6. What is the power set of {0,1,a}?

7. If AB = , what does that tell you about |AB|?