5. (25) Classify each of the following languages as:

(R) Regular, (CF) Context-Free, but not regular,

(REC) Recursive -- Turing-Decidable -- but not context-free,

(R.E.) recursively enumerable -- Turing-Recognizable -- but not Turing-decidable, or (None) None of the above.

Explanation not necessary.

a. {w {0 - 9}* : w, when viewed as a base 10 integer, with no leading zeros, is divisible by 20}.

b, L_writes-0 = { | is a description of a TM and M writes a 0 when run on some string w}

c. L_PLUS = { a^xb^yc^z : x, y, z are integers, z = x+y}

d. L_REJECTS-TWO = { : M rejects at least two strings}

e. L_{PART_REVERSE} = {w = xyx^R : x in{0, 1}⁺=(0|1)*(0|1), y in (0|1)*}

f. L_THIRDS = {wx : |w| = 2|x| , w in a⁺b⁺ , x in a⁺b⁺}

(length of strings divisible by 3, first 2/3 of form a+b+, last third of the form a+b+)

g. L_{TWO-RT_MOVES} = { : M moves right exactly twice while operating on w}

h. L_{LEAP YEAR} = {n : n is a non-negative number denoting a leap year}

A year is a leap year if and only if it is divisible by 4, unless it is divisible by 100, in which case it is not a leap year, unless it is divisible by 400, in which case it is eg 1984, 2000, not 1900, 2010

i. L_{accepts at least 2}= { | M is a Turing Machine that accepts at least two strings}