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?
- Recursive language is closed under complement.
- The complement of a recursively enumerable language is recursively enumerable.
- The complement of a recursive language is either recursive or recursively enumerable.
- 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 only
- 3 only
- 3 and 4 only
- 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?
- Z is recursive, and W can be recursively enumerable.
- Z is recursively enumerable, and W can be recursive.
- Z is recursive, and W is not recursively enumerable.
- 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
- an uncountable set
- Closed under intersection
- closed under complementation.
- 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 = {a^{p} | p is a prime}.
Which of the following is true?
- A Turing Machine does not accept L.
- L is regular but not context-free.
- L is context-free but not regular.
- L is neither regular nor context-free but accepted by a Turing Machine.
Answer: D
Explanation: Given that L = {a^{p} | 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
- I only
- I and III only
- I and IV only
- 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?
- L1 ∪ L2 is context-free.
- L3 ∩ L1 is recursive.
- L1 ∩ , L2 ∩ L3 are recursively enumerable.
- 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?
- Every recursive language is also recursively enumerable language.
- L = {0n1n 0n │n=1, 2 , 3, ....} is recursively enumerable.
- Recursive languages are closed under intersections.
- 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
- Type 0
- Type 1
- Type 2
- 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
- Unified problem
- Boolean function
- Recursive problem
- Decidable
Answer: D
Explanation: Recursive languages are Turing decidable.
11. Of the given pairs, which pair has a DIFFERENT expressive power?
- Single-Tape and Multi-Tape Turing machine
- Deterministic and Non-deterministic pushdown Automata
- Deterministic and Non-deterministic finite automata
- 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-
- Kleene Star
- Intersection
- Union
- 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
- II only
- II and III only
- I and IV only
- 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?
- S1 is correct, but S2 is not correct
- S1 is not correct, but S2 is correct
- Both S1 and S1 are not correct
- 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?
- L2 - L1
- L1 - L3
- L2 ∩ L1
- 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
- Regular
- Context-sensitive
- Context-free
- 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?
- L1' is recursive, and L2' is recursively enumerable
- L1' is recursive, and L2' is not recursively enumerable
- Both L1' and L2' are recursively enumerable
- 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?
- 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
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?
- it may halt and accept the input
- it may halt by changing the input
- it may halt and reject the input
- 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 (L_{RE} ), the context-free language (L_{CF} ), the context-sensitive language (L_{CS} ), deterministic context-free language (L_{DCF} ) and the recursive language (L_{REC} ). The relationship between these families of languages is given by which one of the following?
- L_{CF} ⊆ L_{DCF} ⊆ L_{CS} ⊆ L_{RE } ⊆ L_{REC}
- L_{CF} ⊆ L_{DCF} ⊆ L_{CS} ⊆ L_{REC} ⊆ L_{RE}
- L_{DCF} ⊆ L_{CF} ⊆ L_{CS} ⊆ L_{RE } ⊆ L_{REC}
- L_{DCF} ⊆ L_{CF } ⊆ L_{CS} ⊆ L_{REC} ⊆ L_{RE}
Answer: D
Explanation: According to Chomsky’s hierarchy, we have the following order
L_{DCF} ⊆ L_{CF } ⊆ L_{CS} ⊆ L_{REC} ⊆ L_{RE}
Also check out - Rod Cutting Problem