For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?

L is recursively enumerable, but not recursive

L is recursive, but not context-free

L is context-free, but not regular

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i S1 : L1 is recursive implies L2 is recursive S2 : L2 is recursive implies L1 is recursive Which of the following statements is true ?

S1 is true but S2 is not necessarily true

S2 is true but S1 is not necessarily true

Courses
Tutorials
DSA
Data Science
Web Tech

Recursively enumerable sets and Turing machines

Question 1

Which of the following statements is/are FALSE?

1. For every non-deterministic Turing machine, 
   there exists an equivalent deterministic Turing machine.
2. Turing recognizable languages are closed under union 
   and complementation.
3. Turing decidable languages are closed under intersection 
   and complementation.
4. Turing recognizable languages are closed under union 
   and intersection.

1 and 4 only
1 and 3 only
2 only
3 only

Discuss it

Question 2

Let L1 be a recursive language. Let L2 and L3 be languages that are recursively enumerable but not recursive. Which of the following statements is not necessarily true?

L2 – L1 is recursively enumerable.
L1 – L3 is recursively enumerable
L2 ∩ L1 is recursively enumerable
L2 ∪ L1 is recursively enumerable

Discuss it

Question 3

Which of the following is true for the language

It is not accepted by a Turing Machine
It is regular but not context-free
It is context-free but not regular
It is neither regular nor context-free, but accepted by a Turing machine

Discuss it

Question 4

If L and L' are recursively enumerable, then L is

regular
context-free
context-sensitive
recursive

Discuss it

Question 5

Let L be a language and L' be its complement. Which one of the following is NOT a viable possibility?

Neither L nor L' is recursively enumerable (r.e.).
One of L and L' is r.e. but not recursive; the other is not r.e.
Both L and L' are r.e. but not recursive.
Both L and L' are recursive

Discuss it

Question 6

Let A ≤_m B denotes that language A is mapping reducible (also known as many-to-one reducible) to language B. Which one of the following is FALSE?

If A ≤_m B and B is recursive then A is recursive.
If A ≤_m B and A is undecidable then B is undecidable.
If A ≤_m B and B is recursively enumerable then A is recursively enumerable.
If A ≤_m B and B is not recursively enumerable then A is not recursively enumerable.

Discuss it

Question 7

For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?

L is recursively enumerable, but not recursive
L is recursive, but not context-free
L is context-free, but not regular
L is regular

Discuss it

Question 8

Let L1 be a recursive language, and let L2 be a recursively enumerable but not a recursive language. Which one of the following is TRUE?

L1' --> Complement of L1
L2' --> Complement of L2

L1' is recursive and L2' is recursively enumerable
L1' is recursive and L2' is not recursively enumerable
L1' and L2' are recursively enumerable
L1' is recursively enumerable and L2' is recursive

Discuss it

Question 9

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as w1, w2, w3, ... Define another language L2 over Σ Union {#} as {wi # wj : wi, wj ∈ L1, i < j}. Here # is a new symbol. Consider the following assertions.

S1 :  L1 is recursive implies L2 is recursive
S2 : L2 is recursive implies L1 is recursive

Which of the following statements is true ?

Both S1 and S2 are true
S1 is true but S2 is not necessarily true
S2 is true but S1 is not necessarily true
Neither is necessarily true

Discuss it

Question 10

Nobody knows yet if P = NP. Consider the language L defined as follows : Which of the following statements is true ?

L is recursive
L is recursively enumerable but not recursive
L is not recursively enumerable
Whether L is recursive or not will be known after we find out if P = NP

Discuss it

Get ready to boost your rank and secure an exceptional GATE 2025 score with confidence!

Our GATE CS & IT Test Series 2025 offers 60 PYQs Quizzes, 60 Subject-Wise Mock Tests, 4500+ PYQs and practice questions, and over 20 Full-Length Mock Tests that ensure you’re well-prepared to tackle the toughest questions and secure a top-rank in the GATE 2025 exam. Get personalized insights with student rankings based on performance and benefit from expert-designed tests created by industry pros and GATE CS toppers.

Plus, don’t miss out on these exclusive features:

--> All India Mock Test
--> Live GATE CSE Mentorship Classes
--> Live Doubt Solving Sessions

Join now and stay ahead in your GATE 2025 journey!

1 2 3

There are 29 questions to complete.

Last Updated :

Take a part in the ongoing discussion

Trending in News