EXERCISES
1. Use induction on n to show that |u n | = n |u| for all strings u and all n.
2. The reverse of a string, introduced informally above, can be defined more
precisely by the recursive rules
for all a ∈ ∑, w ∈ ∑*. Use this to prove that
for all u, υ ∈ ∑ + .
3. Prove that (w R ) R = w for all w ∈ ∑*.
4. Let L = {ab, aa, baa}. Which of the following strings are in L*:
abaabaaabaa, aaaabaaaa, baaaaabaaaab, baaaaabaa? Which strings are in
L 4 ?
5. Let ∑ = {a, b} and L = {aa, bb}. Use set notation to describe .
6. Let L be any language on a nonempty alphabet. Show that L and cannot
both be finite.
7. Are there languages for which
8. Prove that
for all languages L 1 and L 2 .
9. Show that (L*)* = L* for all languages.
10. Prove or disprove the following claims.
(a)
for all languages L 1 and L 2 .
(b) (L R )* = (L*) R for all languages L.