Recall warm-up
- Full containment chain?
Stuck? Peek at 4.3.2 The Chomsky hierarchy and the containment chain
- Regular ⊊ DCFL ⊊ CFL ⊊ CSL ⊊ REC ⊊ RE ⊊ all.
- Types: 0 unrestricted/TM/RE; 1 CSG/LBA/CSL; 2 CFG/PDA/CFL; 3 regular grammar/FA/regular.
- Witnesses: aⁿbⁿ, wwᴿ, aⁿbⁿcⁿ, (diagonal), A_TM.
- What does dovetailing do?
Stuck? Peek at 4.3.1 Recursive vs recursively enumerable; deciders and recognizers
- Recognizer: accepts L, may loop outside. RE = recognizable = semi-decidable = enumerable.
- Decider: halts always. Recursive = decidable.
- REC ⊆ RE. Enumerator ⇔ recognizer (dovetailing). Shortlex enumeration ⇔ recursive.
- Are CFLs closed under complement?
Stuck? Peek at 3.4.1 Closure properties of CFLs and DCFLs
- CFL closed: ∪, concat, *, reversal, h, h⁻¹, substitution, ∩R, −R. Not: ∩, complement, difference.
- DCFL closed: complement, ∩R, ∪R, −R, h⁻¹. Not: ∪, ∩, concat, *, reversal, h.
- Counterexample: aⁿbⁿcᵐ ∩ aᵐbⁿcⁿ = aⁿbⁿcⁿ. Non-CFL proof: L ∩ R non-CFL ⇒ L non-CFL.
The Hook
You have a recognizer for “bug-free programs” and another for “buggy programs”. Neither alone may ever finish on some inputs. Run them side by side, one step each in turn: every program is either bug-free or buggy, so one of the two must eventually say yes. Together they form a decider. This little argument is one of the most used theorems in GATE’s decidability questions.
Predict First
To decide w ∈ L ∪ L′ with recognizers M and M′, why can’t you just run M to completion, then M′?
Core Concept
Prediction check
M might loop on w (when w ∉ L), and then M′ never starts even if w ∈ L′. Run them alternately, one step each — then if either accepts, you find out.
Closure of recursive languages
REC is closed under union, intersection, complement (swap accept/reject of a decider), difference, concatenation, Kleene star (try all splits — finitely many), reversal, inverse homomorphism. Not closed under (arbitrary) homomorphism.
Closure of RE languages
RE is closed under union (parallel), intersection (run both, accept if both accept), concatenation, Kleene star (nondeterministically guess splits / dovetail), reversal, homomorphism, inverse homomorphism. Not closed under complement or difference.
| operation | REC | RE |
|---|---|---|
| union | ✓ | ✓ |
| intersection | ✓ | ✓ |
| complement | ✓ | ✗ |
| difference | ✓ | ✗ |
| concatenation | ✓ | ✓ |
| Kleene star | ✓ | ✓ |
| homomorphism | ✗ | ✓ |
| inverse homomorphism | ✓ | ✓ |
| reversal | ✓ | ✓ |
The complement theorem
Proof: run a recognizer for L and one for L̅ alternately on w. Exactly one of w ∈ L, w ∈ L̅ holds, so one machine eventually accepts; answer accordingly. The combined machine always halts. ∎
Four possible situations
For any language L, exactly one holds:
- L and L̅ both recursive.
- L is RE but not recursive ⇒ L̅ is not RE.
- L̅ is RE but not recursive ⇒ L is not RE.
- Neither L nor L̅ is RE.
Impossible: L and L̅ both RE but L not recursive.
| L̅ recursive | L̅ RE, not REC | L̅ not RE | |
|---|---|---|---|
| L recursive | possible | ✗ impossible | ✗ impossible |
| L RE, not REC | ✗ | ✗ | possible |
| L not RE | ✗ | possible | possible |
Putting it together
- REC keeps complement; RE keeps homomorphism; both keep ∪, ∩, concatenation, star.
- Both L and L̅ RE ⇒ L recursive (run alternately).
- An RE-but-not-REC language has a non-RE complement.
Visual
L RE and L̅ RE ⇒ L REC (and L̅ REC) L RE, not REC ⇒ L̅ not RE REC: closed under complement, not homomorphism RE : closed under homomorphism, not complement
Worked Examples
L is recursive. Is L̅ recursive?
Show the full solution
Yes — swap accept and reject.
L is RE and L̅ is RE. Is L recursive?
Show the full solution
Yes, by the complement theorem.
L₁ is RE but not recursive. Which are true? (i) L̅₁ is RE. (ii) L̅₁ is not recursive. (iii) L₁ ∪ L̅₁ is recursive. (iv) L₁ ∩ L₂ is RE for any RE L₂.
Show the full solution
(i) false (else L₁ recursive). (ii) true (complement of a recursive language is recursive). (iii) true: it is Σ*. (iv) true. Answer: (ii), (iii), (iv).
GATE Traps
- RE is NOT closed under complement; REC is.
- REC is NOT closed under homomorphism; RE is.
- L RE and L̅ RE ⇒ L REC — the most tested theorem in this area.
- If L is RE but not REC, then L̅ is not even RE.
Memory Hook
Two detectives, one for guilty and one for innocent: run them in turns and one will always report — together they are a judge.
Connect the Dots
One last idea before Phase 5: a Turing machine can be written down as a string — and a single machine can read that string and simulate any other machine. That universal machine is your computer, and it is the starting point for proving limits.
Self-Test
- MSQ
RE languages are closed under:
- union
- intersection
- complement
- homomorphism
- MCQ
If L and L̅ are both RE, then:
- L is regular
- L is recursive
- L is a CFL
- nothing follows
- MCQ
L is RE but not recursive. L̅ is:
- recursive
- RE but not recursive
- not RE
- regular
- MSQ
Recursive languages are closed under:
- complement
- Kleene star
- homomorphism
- intersection
Rule Card
- REC closed: ∪ ∩ complement − concat * reversal h⁻¹; not h.
- RE closed: ∪ ∩ concat * reversal h h⁻¹; not complement, not difference.
- L, L̅ ∈ RE ⇒ L ∈ REC. L ∈ RE − REC ⇒ L̅ ∉ RE.
Concept Ledger
- closure of recursive languages
- closure of RE languages
- complement theorem (L, L̅ RE ⇒ REC)
- parallel (alternating) simulation
Answer Vault
Reveal answers when you’re ready
Warm-up answers
- Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE.
- Interleaves runs so no single looping run blocks the others.
- No.
Self-test answers
- ABD — Not complement.
- C: Would make every RE language recursive.
- B — Complement theorem.
- A: No.
- C: No.
- D: It follows.
- C — Otherwise L would be recursive.
- A: Then L would be recursive.
- B: Then both RE ⇒ recursive.
- D: No.
- ABD — Not homomorphism.
- C: Not closed.
Flashcards
- If L and L̅ are RE, what is L?
Reveal answer
Recursive. - Is RE closed under complement?
Reveal answer
No. - Is REC closed under homomorphism?
Reveal answer
No (RE is). - L is RE but not REC. L̅?
Reveal answer
Not RE.