CS and IT GATE 2014 Set-2 Questions with Answer

Ques 53 Theory of Computation

---

Let < M > be the encoding of a Turing machine as a string over ∑ = {0, 1}. Let L = {< M > | M is a Turing machine that accepts a string of length 2014}. Then, L is

A

decidable and recursively enumerable

B

undecidable but recursively enumerable

C

undecidable and not recursively enumerable

D

decidable but not recursively enumerable

See Answer Video Solution

Ques 54 Theory of Computation

---

Let L₁ = {w ∈ {0, 1}∗ | w has at least as many occurrences of (110)'s as (011)'s}. Let L₂ = {w ∈ {0, 1}∗ | w has at least as many occurrences of (000)'s as (111)'s}. Which one of the following is TRUE?

A

L₁ is regular but not L₂

B

L₂ is regular but not L₁

C

Both L₁ and L₂ are regular

D

Neither L₁ nor L₂ are regular

See Answer Video Solution