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.
-
The set of strings over alphabet {0, 1} that has equal number of 0’s and 1’s.
-
The set of strings over alphabet {a, b} that starts and ends with the same symbol.
-
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
-
if w = ϵ, wR = ϵ.
-
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.
Reviews
There are no reviews yet.