5. (25) Classify each of the following languages as: (R) Regular, (CF) Context-F

Question

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, Lwrites-0 = { <M,w> | <M> is a description of a TM and M writes a 0 when run on some string w}

   c.    LPLUS = { axbycz : x, y, z are integers, z = x+y}

   d.    LREJECTS-TWO = {<M> : M rejects at least two strings}

   e. LPART_REVERSE = {w = xyxR : x in{0, 1}+=(0|1)*(0|1), y in (0|1)*}

   f.    LTHIRDS = {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. LTWO-RT_MOVES = {<M, w> : M moves right exactly twice while operating on w}

   h. LLEAP 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. Laccepts at least 2= {<M> | M is a Turing Machine that accepts at least two strings}

Explanation / Answer

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

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

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

ANS -  (R.E.) recursively enumerable -- Turing-Recognizable -- but not Turing-decidable,

c) LPLUS = { axbycz : x, y, z are integers, z = x+y}

ANS - Context-Free, but not regular

d) LREJECTS-TWO = {<M> : M rejects at least two strings}

ANS - (R.E.) recursively enumerable -- Turing-Recognizable -- but not Turing-decidable

e) LPART_REVERSE = {w = xyxR : x in{0, 1}+=(0|1)*(0|1), y in (0|1)*}

ANS - (R) Regular

f) LTHIRDS = {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+)

ANS -  Context-Free, but not regular

g) LTWO-RT_MOVES = {<M, w> : M moves right exactly twice while operating on w}

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

Please let me know in case of any clarifications required. Thanks!

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.