Table of contents
1.
Introduction
2.
Recursively enumerable sets and Turing machines questions
3.
FAQs
4.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Recursively enumerable sets and Turing machines Questions

Author Teesha Goyal
0 upvote
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

Introduction

This article will discuss the questions that appeared previously in the gate exam in the theory of computation section. Here we will discuss the questions of recursively enumerable sets and Turing machines. Let's get started and discuss some questions.

Recursively enumerable sets and Turing machines questions

1. Which one of the following is correct?

  1. Recursive language is closed under complement.
  2. The complement of a recursively enumerable language is recursively enumerable.
  3. The complement of a recursive language is either recursive or recursively enumerable.
  4. The complement of a context-free language is context-free.

Answer: A
Explanation: Recursive languages are closed under complement.
 

2. Consider two languages, L1 and L2. L1 is context-free, and L2 is recursively enumerable but not recursive. Which among the following is/are necessarily true?

1. The complement of L1(L1’) is recursive

2. The complement of L2(L2’) is recursive

3. L1’ is context-free

4. L1' ∪ L2 is recursively enumerable

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

Answer: D
Explanation: L1 is context-free, and all context-free languages are also recursive. Recursive languages are closed under complement, so the complement of L1 is also recursive; hence 1 is true. Now, L1 is recursive, so it is also recursively enumerable, and L2 is given to be recursively enumerable. Recursively enumerable languages are closed under union, so L1’ ∪ L2 is also recursively enumerable; hence, 4 is true. Therefore, option D is correct.
 

3. Consider the two languages X and Y. X is a recursive language, and Y is a recursively enumerable language but not recursive. Consider another two languages, W and Z, such that Y' reduces to W and Z reduces to X' (reduction means the standard many to one reduction). Which among the following statements is correct?

  1. Z is recursive, and W can be recursively enumerable.
  2. Z is recursively enumerable, and W can be recursive.
  3. Z is recursive, and W is not recursively enumerable.
  4. Z is not recursive, and W is not recursively enumerable.

Answer: C
Explanation: Given that X is recursive and recursive languages are closed under complement, X’ is also recursive. Z reduces to X’. Therefore Z is also recursive. So our answer is either option A or C. Recursively enumerable languages are not closed under complement, so Y’ is not recursively enumerable. Now Y’ reduces to W, so W  is not recursively enumerable. Therefore, option C is true.
 

4. All recursively enumerable languages are contained in a set that is  

  1. an uncountable set 
  2. Closed under intersection
  3. closed under complementation.
  4. A subset of the set of all recursive languages.

Answer: B
Explanation: Recursively enumerable languages are closed under union, intersection, Kleen star and concatenation but not under complementation. So option B is correct.
 

5. Consider a language L given by 

L = {ap | p is a prime}. 

Which of the following is true?

  1. A Turing Machine does not accept L.
  2. L is regular but not context-free.
  3. L is context-free but not regular.
  4. L is neither regular nor context-free but accepted by a Turing Machine.

Answer: 
Explanation: Given that L = {ap | p is a prime}, Now such a language can only be accepted by a Turing machine and neither by finite Automata nor pushdown automata. Therefore, it is neither regular nor context-free.
 

6. Consider the four languages L1, L2, L3 and L4. L1 is regular, L2 is context-free, L3 is recursive, and L4 is recursively enumerable. Which of the following is/are valid for these languages?

I. L3' U L4 is recursively enumerable

II. L2  U L3 is recursive

III. L1* U L2 is context-free

IV. L1 U L2' is context-free

  1. I only
  2. I and III only
  3. I and IV only
  4. I, II and III only

Answer: D
Explanation: Statement 1 is true: L3 is recursive and recursive languages are closed under complement, so L3’ is also recursive. All recursive languages are recursively enumerable languages, so L3 is also recursively enumerable. Therefore, L3’ U L4 is recursively enumerable as recursively enumerable is closed under union. 

Statement 2 is true: L2 is context-free, so it is also recursive, and L3 is given a recursive language. Recursive language is closed under union, so L2  U L3 is also recursive.

Statement 3 is true: L1 is regular, so it is also context-free. All context-free languages are closed under Kleen star, so L1* is also context-free, and L2 is given context-free. Therefore, L1* U L2 is also context-free as context-free languages are closed under union. 

Statement 4 is not valid: L2 is context-free, and context-free languages are not closed under complement, so L2 may or may not be context-free. Therefore L1 U L2' may or may not be context-free.
 

7. Consider three languages L1, L2 and L3. L1 is a regular language, L2 is a deterministic context-free language, and L3 is a recursively enumerable, but not recursive, language. Which among the following statements is not true?

  1. L1 ∪ L2 is context-free.
  2. L3 ∩ L1 is recursive.
  3. L1 ∩ , L2 ∩ L3 are recursively enumerable.
  4. L1 ∩ L2 is a deterministic CFL.

Answer: B
Explanation: L3 is a recursively enumerable language but not recursive, and L1 is a regular language, so it is recursive. Since L1 is recursive, it is also recursively enumerable. Recursively enumerable language is closed under intersection, so L3 ∩ L1 is recursively enumerable and not recursive. Hence B is not true.
 

8. Which among the following statements is not correct?

  1. Every recursive language is also recursively enumerable language.
  2. L = {0n1n 0n │n=1, 2 , 3, ....} is recursively enumerable.
  3. Recursive languages are closed under intersections.
  4. Recursive languages are not closed under intersections.

Answer: D
Explanation: Recursive languages are closed under intersections, unions, complement, concatenation, Kleen star and set difference. Therefore the answer is option D.
 

9. Consider the grammar with the given production rules

S → Aa

A → Ba

B → abc

The highest type number that can be assigned to this grammar is

  1. Type 0
  2. Type 1
  3. Type 2
  4. Type 3

Answer: D
Explanation: The production rule of the given grammar can be accepted by finite automata, so it is regular grammar. According to Chomsky’s Hierarchy, regular grammar comes under type 3. Hence, option D is correct.
 

10. A recursive language problem is called

  1. Unified problem
  2. Boolean function
  3. Recursive problem
  4. Decidable

Answer: D
Explanation: Recursive languages are Turing decidable.
 

11. Of the given pairs, which pair has a DIFFERENT expressive power?

  1. Single-Tape and Multi-Tape Turing machine
  2. Deterministic and Non-deterministic pushdown Automata
  3. Deterministic and Non-deterministic finite automata
  4. Deterministic and Non-deterministic Single-tape Turing machine

Answer: B
Explanation: All the single tape turning machines can be converted into multi-tape turning machines, so they have the same expressive power; therefore, option A is incorrect. Also, every DFA can be converted to NFA, and every NFA can be converted to DFA; therefore, option C is incorrect. Similarly, option D is incorrect. But not all Non-deterministic pushdown automata can be converted to deterministic pushdown automata. So they have different expressive power. Hence the answer is option B.
 

12. Consider two recursively enumerable languages L and P. The languages L and P are not closed under-

  1. Kleene Star 
  2. Intersection 
  3. Union
  4. Set Difference

Answer: D

Explanation: Recursively enumerable languages are closed under Kleen star, intersection union and concatenation but not set difference.
 

13. Which among the following statements is/are TRUE?

I. Every subset of a recursively enumerable language is also recursive.

II. If a language L and its complement L are recursively enumerable, then L must be recursive.

III. The complement of a context-free language must be recursive

IV. If L1 and L2 are regular, then L1∩ L2 must be deterministic context-free

  1. II only
  2. II and III only
  3. I and IV only
  4. II, III and IV only

Answer: D
Explanation: Statement  I is false: All recursive languages are recursively enumerable, but the reverse is not true, so every subset of the recursively enumerable language is not recursive.

Statement II is true: Recursively enumerable languages are not closed under complement, so if L and L’ both are recursively enumerable, then L must be recursive.

Statement III is true: context-free languages are closed under complement, so the complement of context-free language is also context-free. All context-free languages are recursive. Hence it is true.

Statement IV is true: Regular languages are closed under intersections, so if L1 and L2 are regular, then  L1∩ L2 must be regular. All regular languages are deterministic context-free. Hence, it is true.

Therefore, option D is correct.
 

14. Given the two statements, S1 and S2 

S1: Given two languages, L1 and L2, that are recursively enumerable languages over ∑, then L1 ∪ L 2 and L2 ∩ L2 are always recursively enumerable.

S2: Recursively enumerable language is a countable set.

Which of the two statements is/are correct?

  1. S1 is correct, but S2 is not correct
  2. S1 is not correct, but S2 is correct
  3. Both S1 and S1 are not correct
  4. Both S1 and S1 are correct

Answer: D
Explanation: S1:recursively enumerable languages are closed under union and intersection. Therefore, S1 is correct.

S2: recursively enumerable languages are countable. Hence S2 is also correct.
 

15. Consider three languages L1, L2 and L3. L1 is a recursive language. L2 and L3 are recursively enumerable but not recursive languages. Which one of the following is not a recursively enumerable language?

  1. L2 - L1
  2. L1 - L3
  3. L2 ∩ L1
  4. L2 ∪ L1 

Answer:  B
Explanation: L2 - L1 is valid because recursively enumerable language - recursive language gives recursively enumerable language. L1 is recursive, so it is also recursively enumerable; hence, L2 ∩ L1 and L2 ∪ L1 are also recursively enumerable because recursively enumerable is closed under union and intersection. L1 - L3 is not recursively enumeration because recursively enumerable is not closed under set difference.
 

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

  1. Regular
  2. Context-sensitive
  3. Context-free
  4. Recursive

Answer: D
Explanation: recursively enumerable language is not closed under complement, so if L and L’ both are recursively enumerable, then L must be recursive. 
 

17. Consider two languages, L1 and L2. L1 is recursive, and L2 is recursively enumerable. Which one of the following is true?

  1. L1' is recursive, and L2' is recursively enumer­able
  2. L1' is recursive, and L2' is not recursively enumerable
  3. Both L1' and L2' are recursively enumerable
  4. L1' is recursively enumerable, and L2' is recursive

Answer: B
Explanation: L1’ is recursive, and L2’ is not recursive because recursive languages are closed under complement, but recursively enumerable languages are not closed under complement.
 

18. It is not known yet if P = NP. Consider a language L defined as -

L = { (0 +1)*  if P =NP ; Ⲫ  otherwise}

Which of the following statements is true?

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

Answer: A
Explanation: In the given language, the language is regular in both the cases P = NP and P != NP, the language is regular; hence, we can say that L is recursive.
 

19. For a given input, which of the following is false to possible outcomes when executing a Turing machine?

  1. it may halt and accept the input
  2. it may halt by changing the input
  3. it may halt and reject the input
  4. it may never halt

Answer: B
Explanation: Turning machines halts when we change the input, and since we don't know what kind of outcome the given turning machine will produce on any input, halting is undecidable. Therefore, we don't know whether it accepts or rejects, so it is good to say that the turning machine may half by changing the input. Hence, option B is correct. 
 

20. Given the recursively enumerable language (LRE ), the context-free language (LCF ), the context-sensitive language (LCS ), deterministic context-free language (LDCF ) and the recursive language (LREC ).  The relationship between these families of languages is given by which one of the following?

  1. LCF  ⊆  LDCF  ⊆  LCS  ⊆  LRE  ⊆  LREC
  2. LCF  ⊆  LDCF  ⊆  LCS  ⊆  LREC  ⊆  LRE
  3. LDCF ⊆  LCF   ⊆  LCS  ⊆  LRE  ⊆ LREC
  4. LDCF ⊆  LCF   ⊆  LCS   ⊆  LREC  ⊆  LRE

Answer: D
Explanation: According to Chomsky’s hierarchy, we have the following order

LDCF ⊆  LCF   ⊆  LCS   ⊆  LREC  ⊆  LRE


Also check out - Rod Cutting Problem

FAQs

  1. What is the theory of computation?
    Theory of computation is a field of computer science that deals with the study of abstract machines and the computational problem that can be solved using these machines.
     
  2. What is the order specified by Chomsky’s Hierarchy?
    According to Chomsky’s hierarchy, we have the following order is LDCF ⊆  LCF   ⊆  LCS   ⊆  LREC  ⊆  LRE
     
  3. Recursively enumerable languages are closed under what operations?
    Recursively enumerable languages are closed under Kleen star, union, intersection and concatenation.
     
  4. Recursive languages are closed under what operations?
    Recursively languages are closed under Kleen star, union, intersection, complement, set difference and concatenation.

Key Takeaways

In this article, we discussed the previous year's gate questions on recursively enumerable sets and Turing machines. We have discussed the answers to the questions with an explanation. Hope you would have gained a better understanding of these topics now!

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? 

Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Happy Coding!

Live masterclass