The master decidability table

1. Rice’s theorem in one line?
   Stuck? Peek at 5.4 Rice’s theorem and the Post Correspondence Problem

   • Rice: non-trivial property of L(M) ⇒ undecidable. Not for code/bounded-behaviour properties or trivial ones.
   • ≠ ∅, contains w: RE. = ∅, finite, = Σ*, regular, CFL: not RE.
   • PCP: undecidable (|Σ| ≥ 2), RE; unary decidable. Used for CFG ambiguity, CFL ∩ emptiness, CFG universality.

   Read lesson 5.4

2. Which CFG questions have algorithms?
   Stuck? Peek at 3.4.2 Algorithms for CFLs: emptiness, finiteness, membership (CYK)

   • Emptiness: is S generating? Finiteness: cycle in the cleaned variable graph. Membership: CYK O(n³|G|), CNF required.
   • No algorithm for general CFGs: equivalence, universality, ambiguity, regularity, emptiness of intersection.

   Read lesson 3.4.2

3. Is equivalence of two DFAs decidable?
   Stuck? Peek at 2.4.2 Algorithms for regular languages

   • Membership: run. Emptiness: reachable F? Finiteness: trim + cycle (or lengths n..2n−1). Universality: complement + emptiness. Equivalence: minimize & compare, or symmetric difference empty. Containment: L₁ ∩ L̅₂ = ∅.
   • All these have always-terminating algorithms for regular languages.

   Read lesson 2.4.2

GATE’s favourite decidability question is a grid: “Which of these problems is decidable?” with a mix of machine types. Instead of reasoning from scratch each time, you will carry one table in your head — and the three reasons that generate it.

Is emptiness decidable for context-sensitive languages? (Hint: CSLs sit between CFLs and recursive languages.)

Prediction check

No. Membership is decidable for CSLs (LBAs have finitely many configurations), but emptiness for LBAs is undecidable. CSL is where emptiness flips from D to U.

The table

D = decidable, U = undecidable. Columns are language classes (given by their machines or grammars).

Where the boundaries come from

• Membership: decidable up to REC (by definition of REC); for RE only semi-decidable (A_TM).
• Emptiness / finiteness: graph/reachability for FA and CFG; for LBA and TM, Rice/reduction ⇒ U.
• Equivalence / universality: DFA minimization; DCFL via complement (equivalence of DPDAs is decidable — a deep 1997 result); for CFGs, PCP ⇒ U.
• Containment / disjointness for DCFLs: U (intersection of two DCFLs is not controllable).
• Regularity: trivial for regular; decidable for DCFL; U for CFL and above.
• Ambiguity: regular grammars via DFAs, DCFLs have unambiguous grammars ⇒ D; CFG ambiguity ⇒ U (PCP).

Other frequently asked cases

• “Does DFA M accept w / accept anything / accept Σ*?” — all decidable (the inputs are DFAs).
• “Does PDA P accept w?” — decidable (CYK). “Is L(P) = Σ*?” — undecidable.
• “Does TM M accept w?” — undecidable (but RE). “Does M halt on w within k steps?” — decidable.
• “Is L(G₁) ∩ L(G₂) = ∅ for CFGs?” — undecidable. “Is L(G) ∩ R = ∅ for regular R?” — decidable (product is a CFL).
• “Is the complement of a CFL empty?” = universality — undecidable.

The full picture

Everything in one 3D view: every class, the named undecidable languages, and the non-RE region outside.

Putting it together

• Membership fails only at RE; emptiness and finiteness fail at CSL; equivalence, universality, regularity, ambiguity fail at CFL.
• Containment and disjointness fail already at DCFL.
• Bounded questions and questions about DFAs/PDA membership stay decidable.

           Reg  DCFL  CFL  CSL  REC  RE
member      D    D     D    D    D    U
empty       D    D     D    U    U    U
finite      D    D     D    U    U    U
equal       D    D     U    U    U    U
= Σ*        D    D     U    U    U    U
⊆           D    U     U    U    U    U
∩ = ∅       D    U     U    U    U    U
regular?    D    D     U    U    U    U
ambiguous?  D    D     U    U    U    U
mnemonic: membership falls last (only RE), emptiness at CSL, equality/universality at CFL, ⊆ and ∩ already at DCFL.

Phase 5 complete — and with it, the whole syllabus. Phase 6 merges every rule card into one master sheet, mixes questions from all phases, drills the recurring GATE patterns, and ends with the 30-question final test.

1. MSQ

   Which are decidable for CFLs?

   1. membership
   2. emptiness
   3. equivalence
   4. finiteness
2. MCQ

   For CSLs, which is decidable?

   1. emptiness
   2. membership
   3. equivalence
   4. finiteness
3. MCQ

   For RE languages, membership is:

   1. decidable
   2. undecidable (but semi-decidable)
   3. trivial
   4. not RE
4. MSQ

   Which are undecidable?

   1. CFG universality
   2. DFA equivalence
   3. CFG ambiguity
   4. DCFL containment
5. MCQ

   Equivalence of DCFLs is:

   1. decidable
   2. undecidable
   3. decidable only for regular DCFLs
   4. not well-defined

• master decidability table
• decidability boundary by class

1. Where does emptiness become undecidable?
   Reveal answer

   At CSL (LBA emptiness).
2. Is CSL membership decidable?
   Reveal answer

   Yes.
3. Is DCFL equivalence decidable?
   Reveal answer

   Yes.
4. Is DCFL containment decidable?
   Reveal answer

   No.
5. Is CFG universality decidable?
   Reveal answer

   No.