Let Here, 2 contains all columns of 0s and 1s of height two. A string of

Let

 

Here, Σ₂ contains all columns of 0s and 1s of height two. A string of symbols in Σ₂ gives two rows of 0s and 1s. Consider each row to be a binary number and let

C = {w ∈ Σ^*₂| the bottom row of w is three times the top row}.

For example,

Show that C is regular. You may assume the result claimed in Problem 1.31.

Problem 1.31.

For any string w = w₁w₂ · · ·w_n, the reverse of w, written w^R, is the string w in reverse order, w_n · · ·w₂w₁. For any language A, let A^R = {w^R| w ∈ A}. Show that if A is regular, so is A^R.

Transcribed Image Text:

E2 = {[:], [:], [3], [H} .