The Chomsky hierarchy and the containment chain

1. What is a decider?
   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.

   Read lesson 4.3.1

2. Which machine accepts exactly the CSLs?
   Stuck? Peek at 4.2 TM variants, linear bounded automata and context-sensitive languages

   • Multi-tape (O(t²)), nondeterministic (BFS, exponential), two-way tape, 2-stack PDA, 2 counters: all = TM.
   • LBA: nondeterministic TM within the input ⇔ CSG (|α| ≤ |β|) ⇔ CSL.
   • CFL ⊊ CSL (aⁿbⁿcⁿ). Every CSL is decided by an always-halting TM.

   Read lesson 4.2

3. Regular ⊂ DCFL ⊂ CFL — which language separates DCFL from CFL?
   Stuck? Peek at 3.3.3 Designing PDAs; DPDA vs NPDA; DCFL ⊂ CFL

   • Recipe: stack stores what is unbounded; states store the phase; Z₀ detects empty; accept via ε, Z₀.
   • DPDA: ≤ 1 move per (q, a|ε, X), and no ε-move competing with input moves.
   • Regular ⊊ DCFL ⊊ CFL. wwᴿ, aⁿbⁿ ∪ aⁿb²ⁿ, aⁱbʲcᵏ (i=j or j=k): CFL not DCFL.
   • DCFL ⇒ unambiguous grammar; not conversely.

   Read lesson 3.3.3

GATE’s most reused one-mark fact is a single line: Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE, each inclusion strict. Noam Chomsky organized the grammar side into four types in 1956; the machines you met line up with them exactly. This lesson builds the full picture — in 3D.

Which language would you use to show CSL ≠ CFL? And CFL ≠ DCFL?

Prediction check

aⁿbⁿcⁿ is context-sensitive but not context-free; wwᴿ is context-free but not deterministic. Each strict step has a standard witness.

The four grammar types

DCFL and REC are not Chomsky types but sit in the chain: DCFL between regular and CFL; REC between CSL and RE.

See it in 3D

Each class is a shell inside the next. Tap a shell to see its machine, closure properties and example languages; tap a glowing point to see why a language lives where it does.

Unrestricted grammars = TMs

Type-0 grammars allow any rule α → β (α non-empty). A TM can search all derivations (so grammar ⇒ RE); a grammar can simulate a TM run backwards (RE ⇒ grammar).

Reading the chain in exam questions

• “Every CFL is recursive” — true (CFL ⊂ CSL ⊂ REC).
• “Every RE language is CSL” — false.
• “Every DCFL is a CSL” — true.
• “Complement of a CFL is a CSL” — true (complement of a CSL is a CSL).

Putting it together

• Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE, every step strict.
• Chomsky types 3→0 match FA, PDA, LBA, TM.
• Each step has a standard witness language.

Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE ⊂ all languages
  DFA     DPDA   NPDA   LBA   decider  TM
  a*b*    aⁿbⁿ   wwᴿ    aⁿbⁿcⁿ   (diag.)  A_TM (Phase 5)

Which operations keep a language recursive, or RE? And a key bridge theorem: if both L and its complement are RE, then L is recursive.

1. MCQ

   Correct containment chain:

   1. Reg ⊂ CFL ⊂ DCFL ⊂ CSL ⊂ REC ⊂ RE
   2. Reg ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE
   3. Reg ⊂ DCFL ⊂ CFL ⊂ REC ⊂ CSL ⊂ RE
   4. Reg ⊂ CSL ⊂ CFL ⊂ REC ⊂ RE
2. MSQ

   Which are true?

   1. Every CSL is recursive
   2. Every RE language is recursive
   3. Every DCFL is a CSL
   4. Type 0 grammars generate exactly the RE languages
3. MCQ

   Which machine corresponds to Type 1 grammars?

   1. DFA
   2. PDA
   3. LBA
   4. TM
4. MCQ

   A language in CSL but not in CFL:

   1. aⁿbⁿ
   2. wwᴿ
   3. aⁿbⁿcⁿ
   4. a*b*

• Chomsky hierarchy (Type 0–3)
• unrestricted grammar
• containment chain Reg ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE

1. Full containment chain?
   Reveal answer

   Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ REC ⊂ RE (all strict).
2. Type 1 grammars and machines?
   Reveal answer

   Context-sensitive grammars, LBAs.
3. Witness for CFL ⊊ CSL?
   Reveal answer

   aⁿbⁿcⁿ (or ww).