COM S 331: Theory of Computing, Summer 2021 Homework Assignment 1

Due at 11:59PM, Wednesday, May 19, on Gradescope.

Problem 1 (20 points). Give an example of two non-empty unequal languages A, B ⊆ {0, 1}∗ such that AB = BA. Show why your examples of A and B satisfy the requirements.

Problem 2 (30 points). Write formal descriptions of the following sets.

1. The set of strings over alphabet {0, 1} that has equal number of 0’s and 1’s.

2. The set of strings over alphabet {a, b} that starts and ends with the same symbol.

3. The set of stings over alphabet {a, b, c} which is equal to its reverse.

Problem 3 (25 points). We formally define the reverse wR of a string w as

1. if w = ϵ, wR = ϵ.

2. if w = au for some a ∈ Σ and some u ∈ Σ∗, wR = uRa. Prove: that for any strings x, y ∈ Σ∗, (xy)R = yRxR.

Problem 4 (25 points). Prove: If A = {a, b} and B ⊆ {a, b}∗, then

A∗ = B∗ ⇒ A ⊆ B.