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

Updated 9 Sep 20268 min read
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. 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.

Dovetailing table for input 1010: M_A accepts at round 3 while M_B keeps running; union accepts and intersection waits.

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 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.

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. 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.

Solved page

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.

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 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.

Solved page

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.

Solved page

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.

Solved page

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).

Solved page

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.

Solved page

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

Closure table showing recursive languages closed under union, intersection, complement and difference, while RE languages lack general complement and difference closure.

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.