Closure Properties MCQs for Turing Machines: 12 Solved Questions

A flat closure table is easy to memorise, but equally easy to misuse when an option silently switches from recursive, meaning decidable, to recursively enumerable, meaning Turing-recognisable. The 12 questions below come from KnowledgeGate's live bank of over 30 published questions on Turing machine closure properties. Attempt each one before reading the answer-first explanation. Every question also links to its own live solved page for further practice.

1. Read this closure map before attempting the MCQs

A recursive language is decidable: its machine halts on every input. Recursive languages are closed under union, intersection, complement, and difference because their deciders finish.

A recursively enumerable language is Turing-recognisable. Its recogniser accepts members but may loop on non-members. Dovetailing two recognisers proves closure under union and intersection, but not complement or difference.

If both L and complement(L) are recursively enumerable, then L is recursive. Dovetail their recognisers; exactly one eventually accepts, so the combined machine always halts correctly.

Let D_even decide whether a binary string has an even number of 1s, and D_end0 whether it ends in 0. On 1010, the first counts two 1s and the second reads the final 0; both accept, so union and intersection accept. On 111, both reject, while complement(D_even) accepts. Every component halts.

2. Questions 1-3: the complement fault line

Q1. Recursive versus recursively enumerable under complement

Given the following statements: (i) Recursive enumerable sets are closed under complementation. (ii) Recursive sets are closed under complementation. Which is/are the correct statements?

• (a) only (i)

• (b) only (ii)

• (c) both (i) and (ii)

• (d) neither (i) nor (ii)

Answer: (b) only (ii)

A decider always halts, so swapping accept and reject decides its complement. An RE recogniser may loop on a non-member; relabelling states cannot turn that loop into acceptance. Thus (i) is false and (ii) true.

Solved page

Q2. Which operation breaks RE closure?

If L and P are two recursively enumerable languages, then they are not closed under

• (a) Kleene Star L * of L

• (b) Intersection L ∩ P

• (c) Union L ∪ P

• (d) Set Difference

Answer: (d) Set Difference

Dovetailing proves RE closure under union and intersection; enumerating finite decompositions proves Kleene-star closure. But L - P = L intersection complement(P), and complement(P) need not be RE. Complement is the blocker.

Solved page

Q3. Fill the non-closure operation

There exist a recursive enumerable language whose __________ is not recursively enumerable.

• (a) Union

• (b) Intersection

• (c) Complementation

• (d) Concatenation

Answer: (c) Complementation

The standard witness A_TM = {<M,w> | M accepts w} is recognisable but undecidable. If its complement were recognisable, dovetailing both recognisers would reveal which side contains <M,w> and decide A_TM, a contradiction. Union, intersection, and concatenation remain RE.

Solved page

3. Questions 4-6: intersection, union, and countability

Q4. One true property of all RE languages

The set of all recursively enumerable languages is

• (a) closed under complementation.

• (b) closed under intersection.

• (c) a subset of the set of all recursive languages.

• (d) an uncountable set.

Answer: (b) closed under intersection.

Dovetail two recognisers and accept after both accept, proving intersection closure. RE lacks complement closure, and recursive languages are a subset of RE, not the reverse. Because finite strings are countable, finite machine encodings also make the machines and RE languages countable.

Solved page

Q5. Test three closure statements independently

Consider the following statements:I. Recursive languages are closed under complementationII. Recursively enumerable languages are closed under unionIII. Recursively enumerable languages are closed under complementationWhich of the above statements are true?

• (a) I only

• (b) I and II

• (c) I and III

• (d) II and III

Answer: (b) I and II

I is true because a halting decider's outcomes can be swapped. II follows by dovetailing two recognisers. III is false because a recogniser may loop on rejection. Thus (T, T, F) maps only to (b).

Solved page

Q6. Closure plus the size of the RE family

Given the following two statements:𝑆1: If 𝐿1 and 𝐿2 are recursively enumerable languages over Σ, then 𝐿1 ∪ 𝐿2 and 𝐿1 ∩ 𝐿2 are also recursively enumerable.𝑆2: The set of recursively enumerable languages is countable.Which of the following is true ?

• (a) 𝑆1 is correct and 𝑆2 is not correct

• (b) 𝑆1 is not correct and 𝑆2 is correct

• (c) Both 𝑆1 and 𝑆2 are not correct

• (d) Both 𝑆1 and 𝑆2 are correct

Answer: (d) Both 𝑆1 and 𝑆2 are correct

Union accepts when either dovetailed recogniser accepts; intersection waits for both. Each Turing machine is a finite string over a finite alphabet, so machines, and the languages they recognise, form countable sets.

Solved page

4. Questions 7-9: mixed families and set difference

Q7. Find the one false closure statement

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.

• (a) 1 and 4 only

• (b) 1 and 3 only

• (c) 2 only

• (d) 3 only

Answer: (c) 2 only

Deterministic and nondeterministic Turing machines recognise the same class, so 1 is true. Recognisable languages are closed under union but not complement, so 2 is false. Deciders satisfy 3, and dovetailing proves 4. Only 2 fails.

Solved page

Q8. Difference with one decidable operand

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?

• (a) L2 – L1 is recursively enumerable

• (b) L1 – L3 is recursively enumerable

• (c) L2 ∩ L1 is recursively enumerable

• (d) L2 ∪ L1 is recursively enumerable

Answer: (b) L1 – L3 is recursively enumerable

L2 - L1 is RE because it intersects L2 with recursive complement(L1). Intersection and union with L1 also preserve RE. For (b), choose L1 = {0,1}* and RE, non-recursive L3 = K; then L1 - L3 = complement(K), which is not RE.

Solved page

Q9. Combine a CFL with an RE language

For any two languages $L_1$ and $L_2$ such that $L_1$ is context-free and $L_2$ is recursively enumerable but not recursive, which of the following is/are necessarily true?I. $\overline L_1$ (complement of $L_1$) is recursiveII. $\overline L_2$ (complement of $L_2$) is recursiveIII. $\overline L_1$ is context-freeIV. $​​\overline L_1 \cup L_2$ is recursively enumerable

• (a) I only

• (b) III only

• (c) III and IV only

• (d) I and IV only

Answer: (d) I and IV only

Every CFL is decidable, so complement(L1) is recursive: I is true. CFLs lack complement closure, so III is not guaranteed. A recursive complement(L2) would make L2 recursive, so II is false. Finally, recursive complement(L1) union RE L2 is RE, proving IV.

Solved page

5. Questions 10-12: implication chains examiners hide inside options

Q10. Four language classes in one statement set

Consider the following types of languages: $L_1$ : Regular, $L_2$ : Context-free, $L_3$ : Recursive, $L_4$ : Recursively enumerable. Which of the following is/are TRUE?I. $\overline L_3 \cup L_4$ is recursively enumerableII. $L_2 \cup L_3$ is recursiveIII. $L_1^* \cup L_2$ is context-freeIV. $L_1 \cup \overline L_2$ is context-free

• (a) I only

• (b) I and III only

• (c) I and IV only

• (d) I, II and III only

Answer: (d) I, II and III only

I holds because complement(L3) is recursive, hence RE, and union preserves RE. II holds because every CFL is recursive. III holds because L1* is regular and CFLs are closed under union with regular languages. IV can fail because CFLs lack complement closure.

Solved page

Q11. The L and complement(L) theorem

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

• (a) Neither $L$ nor $\overline L$ is recursively enumerable (r.e.).

• (b) One of $L$ and $\overline L$ is r.e. but not recursive; the other is not r.e.

• (c) Both $L$ and $\overline L$ are r.e. but not recursive.

• (d) Both $L$ and $\overline L$ are recursive.

Answer: (c) Both $L$ and $\overline L$ are r.e. but not recursive.

Dovetail recognisers for both sides on w. Exactly one side contains w, so one recogniser eventually accepts; accept for the L recogniser and reject for the complement recogniser. This always halts, making L recursive and contradicting (c).

Solved page

Q12. Difference and countability together

Assume statements S₁ and S₂ defined as:S₁: L₂ − L₁ is recursively enumerable, where L₁ and L₂ are recursive and recursively enumerable respectivelyS₂: The set of all Turing machines is countableWhich of the following is true?

• (a) S₁ is correct and S₂ is not correct

• (b) Both S₁ and S₂ are correct

• (c) Both S₁ and S₂ are not correct

• (d) S₁ is not correct and S₂ is correct

Answer: (b) Both S₁ and S₂ are correct

For S₁, L2 - L1 intersects RE L2 with recursive, hence RE, complement(L1). For S₂, finite machine encodings over a finite alphabet form a countable set.

Solved page

6. Compress the 12 solutions into one revision table

Remember these traps:

• recursive is a subset of RE

• a recogniser may loop on non-members

• both L and complement(L) in RE implies L is recursive

7. Short version and next practice step

Deciders halt, making Boolean operations safe. Dovetail recognisers for union and intersection; complement is the boundary, and difference inherits its problem. Rebuild the table, then continue with the Theory of Computation / Automata Theory course. For the complement theorem, read Turing Machines and Decidability, then practise through the CS Fundamentals category.