PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q14(b)

Theory of Computation · 2 marks

Open in the Padhaiko app

Topic: TM Variants, Unrestricted Grammar, Chomsky Hierarchy & Recursive Functions

Question

Explain the closure properties of recursively enumerable languages.

Solution

Closed Operations for Recursively Enumerable Languages: A language is Recursively Enumerable (RE) if it is accepted by some Turing Machine. The RE languages are closed under:

  1. Union (): Closed. Construct a 2-tape TM (or dovetail a 1-tape TM) that simulates and on input in parallel. If either halts and accepts, accept.
  2. Intersection (): Closed. Run on . If accepts, run on . If also accepts, accept.
  3. Concatenation (): Closed. Nondeterministically split into and run on and on .
  4. Kleene Star (): Closed. Nondeterministically partition and verify that each .

Non-Closure Property: Complementation: Recursively Enumerable languages are not closed under complementation:

Answer:

Recursively Enumerable (RE) languages are closed under union, intersection, concatenation, and Kleene star. They are NOT closed under complementation because if both and were RE, would be decidable, which contradicts the existence of undecidable RE languages (e.g., ).

All past exam questions for Theory of Computation