Chapter recap
All unbounded TM variants (multi-tape, nondeterministic, two-way, 2-stack PDA) are equivalent; LBAs (tape = input) accept the CSLs (non-contracting grammars). Deciders halt always (recursive = decidable); recognizers may loop (RE = semi-decidable = enumerable). Chain: Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE. REC closed under complement, not homomorphism; RE closed under homomorphism, not complement. L and L̅ both RE ⇒ L recursive.
Merged rule card
From 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.
From 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.
From 4.3.3 Closure of REC and RE; L and L̅ both RE ⇒ L recursive
- 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.
Practice questions
- MCQ
Which is NOT equivalent to a standard TM?
- 3-tape TM
- nondeterministic TM
- PDA with 2 stacks
- PDA with 1 stack
- MSQ
Which are recursive?
- every CFL
- every CSL
- every regular language
- every RE language
- MCQ
L̅ is RE and L is RE. L is:
- not RE
- recursive
- regular
- context-free
- MSQ
RE is closed under:
- Kleene star
- complement
- concatenation
- difference
- MCQ
An LBA accepts exactly:
- regular languages
- CFLs
- CSLs
- RE languages
- NAT
In the four-situation grid for (L, L̅), how many combinations are possible (out of 9 cells)?
Write your answer before opening the key.
- MCQ
Type 0 grammars generate:
- CSLs
- recursive languages
- RE languages
- CFLs
- MCQ
Recursive languages are NOT closed under:
- complement
- union
- homomorphism
- intersection
Answer key
Reveal answers when you’re ready
- D — One stack gives CFLs only.
- A: Equivalent.
- B: Equivalent.
- C: Equivalent.
- ABC — REC ⊊ RE.
- D: Not all.
- B — Complement theorem.
- A: It is RE.
- C: No.
- D: No.
- AC — Not complement or difference.
- B: No.
- D: No.
- C — Definition.
- A: Too small.
- B: Too small.
- D: Too big.
- 4 — Both REC; L RE−REC & L̅ not RE; L not RE & L̅ RE−REC; both not RE.
- C — Unrestricted ⇔ TM.
- A: Type 1.
- B: No grammar type matches REC exactly.
- D: Type 2.
- C — Homomorphism can make RE languages.
- A: Closed.
- B: Closed.
- D: Closed.