Closure Properties MCQs for Turing Machines: 12 Solved Questions
Test the closure rules that separate decidable and Turing-recognisable languages. These 12 solved MCQs show how complement, difference, dovetailing, and countability shape the answers.
KnowledgeGate Team
Exam prep & CS education

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. Solve these twelve questions before reading each answer-first explanation. This set focuses on closure behaviour for recursive and Turing-recognisable languages, including complement, difference, dovetailing, and countability. The earlier Closure Properties MCQs: 12 Solved CFL Questions covers context-free operations, while this set stays with Turing-machine language classes.
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.
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 intersection P
(c) Union L union 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.
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.
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.
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).
Q6. Closure plus the size of the RE family
Given the following two statements. S1: If L1 and L2 are recursively enumerable languages over Sigma, then L1 union L2 and L1 intersection L2 are also recursively enumerable. S2: The set of recursively enumerable languages is countable. Which statement is true?
(a) S1 is correct and S2 is not correct
(b) S1 is not correct and S2 is correct
(c) Both S1 and S2 are not correct
(d) Both S1 and S2 are correct
Answer: (d) Both S1 and S2 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.
4. Questions 7-9: mixed families and set difference
Q7. Find the one false closure statement
Which statements are FALSE? 1. For every nondeterministic Turing machine, an equivalent deterministic Turing machine exists. 2. Turing-recognisable languages are closed under union and complementation. 3. Turing-decidable languages are closed under intersection and complementation. 4. Turing-recognisable 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.
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 intersection L1 is recursively enumerable
(d) L2 union 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.
Q9. Combine a CFL with an RE language
For any two languages L1 and L2 such that L1 is context-free and L2 is recursively enumerable but not recursive, which statements are necessarily true? I. complement(L1) is recursive. II. complement(L2) is recursive. III. complement(L1) is context-free. IV. complement(L1) union L2 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.
5. Questions 10-12: implication chains examiners hide inside options
Q10. Four language classes in one statement set
Consider the following language classes: L1 is regular, L2 is context-free, L3 is recursive, and L4 is recursively enumerable. Which statements are TRUE? I. complement(L3) union L4 is recursively enumerable. II. L2 union L3 is recursive. III. L1 star union L2 is context-free. IV. L1 union complement(L2) 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.
Q11. The L and complement(L) theorem
Let L be a language and complement(L) be its complement. Which one of the following is NOT a viable possibility?
(a) Neither L nor complement(L) is recursively enumerable (r.e.).
(b) One of L and complement(L) is r.e. but not recursive; the other is not r.e.
(c) Both L and complement(L) are r.e. but not recursive.
(d) Both L and complement(L) are recursive.
Answer: (c) Both L and complement(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).
Q12. Difference and countability together
Assume statements S1 and S2. S1: L2 - L1 is recursively enumerable, where L1 is recursive and L2 is recursively enumerable. S2: The set of all Turing machines is countable. Which statement is true?
(a) S1 is correct and S2 is not correct
(b) Both S1 and S2 are correct
(c) Both S1 and S2 are not correct
(d) S1 is not correct and S2 is correct
Answer: (b) Both S1 and S2 are correct
For S1, L2 - L1 intersects RE L2 with recursive, hence RE, complement(L1). For S2, finite machine encodings over a finite alphabet form a countable set.
6. Compress the 12 solutions into one revision table
Operation | Recursive / decidable | Recursively enumerable / recognisable | Proof or failure mechanism |
|---|---|---|---|
Union | Closed | Closed | run both deciders; recognisers use dovetailing and accept when either accepts |
Intersection | Closed | Closed | run both deciders; recognisers use dovetailing and wait for both |
Complement | Closed | Not closed in general | swap outcomes only when every branch halts |
Difference | Closed | Not closed in general | A - B = A intersection complement(B), so complement is the blocker |
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.
Keep learning
Turing Machine Decision Properties MCQs: 12 Solved Questions with Explanations
Solve 12 Turing machine Decision Properties MCQs with explanations of bounded simulation, Rice's theorem, complements, dovetailing and mapping reductions.
Turing Machines in Theory of Computation: Design, Worked Trace and Decidability
A six-state Turing machine for L = {0^n1^n}: built from the seven-tuple, traced move by move on 0011 to XXYY and q_accept, then proved a decider rather than only a recogniser.
Turing Machines and Decidability: recursive vs RE, and the halting problem
Turing machines and decidability explained: TM definition and configurations, recursive vs recursively enumerable languages, the halting problem, reductions.
Transitive Relation MCQs: 12 Solved Questions on Definition, Count, Properties and Closure
Test transitivity by finding required shortcut pairs, decisive counterexamples and reachable paths. These 12 MCQs cover relation audits, properties and closure.





