Description

2. Let
.
So Σ contains all columns of 0s and 1s of height two. A string of symbols in Σ give two rows of 0s and
1s. Consider each row to be a binary number and let
C = {w ∈ Σ∗|the bottom row is three times the top row}.
For example, because the binary number 0110 is three times the binary number
0010, but because the binary number 110 is not three times the binary number 001. Show that C is regular.
AR = {wR| wR = wn …w2w1 where w = w1w2 …wn ∈ A},
3. Let Σ be as in the previous problem, and let
E = {w ∈ Σ∗|the bottom row of w is the reverse of the top row of w}.
Show that E is not regular.
1