High yield ●●●

🧬 Language Hierarchy & Closure Tables

Why it matters: One table to rule them all: closure and decidability properties of every class, plus classifying a language.

Subtopics

Each subtopic has its own page: idea, why, how, example, play, check. Mark each one understood when it clicks. 0 of 4 done.

Formulas

Inclusion chain
Regular ⊂ DCFL ⊂ CFL ⊂ CSL ⊂ Recursive ⊂ RE ⊂ all languages
Machines
FA, DPDA, NPDA, LBA, TM (halting), TM
Key facts
L and L̄ both RE ⇒ L recursive; recursive closed under complement; RE not

What GATE asks from this

Question types seen repeatedly in past papers. More stars means more frequent.

★★★
Statement about closure of a class
True/false on ∪, ∩, complement, concatenation for CFL, DCFL, recursive, RE.
★★★
Which of these languages are CFL / regular / decidable
Classify 3–4 languages and pick the correct combination.
★★★
Decidability of problems per class
Is emptiness / equivalence decidable for DFA, PDA, TM?

Ratings are approximate, based on recurring patterns in past GATE CSE papers.

Previous year questions

7 real questions from the official GATE CSE papers (2012 to 2025), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.

7 questions · 0 correct of 0 attempted · marks 0 / 9

Year:
GATE 2025 CS2 · Q25MCQ1 mark
Let G1, G2 be Context Free Grammars (CFGs) and R be a regular expression. For a grammar G, let L(G) denote the language generated by G. Which ONE among the following questions is decidable?
GATE 2025 CS2 · Q30MSQ1 mark
Consider the two lists List I and List II given below. List I: (i) Context free languages, (ii) Recursive languages, (iii) Regular languages. List II: (a) Closed under union, (b) Not closed under complementation, (c) Closed under intersection. For matching of items in List I with those in List II, which of the following option(s) is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2024 CS1 · Q59NAT2 marks
Let G = (V, Σ, S, P) be a context-free grammar in Chomsky Normal Form with Σ = {a, b, c} and V containing 10 variable symbols including the start symbol S. The string w = a30b30c30 is derivable from S. The number of steps (application of rules) in the derivation S ⇒* w is ______.
GATE 2023 · Q24MSQ1 mark
Which of the following statements is/are CORRECT?

One or more options may be correct. Select all that apply, then submit.

GATE 2022 · Q23MSQ1 mark
Which of the following statements is/are TRUE?

One or more options may be correct. Select all that apply, then submit.

GATE 2019 Set 2 · Q34MCQ2 marks
Consider the following sets: S1. Set of all recursively enumerable languages over the alphabet {0, 1}. S2. Set of all syntactically valid C programs. S3. Set of all languages over the alphabet {0, 1}. S4. Set of all non-regular languages over the alphabet {0, 1}. Which of the above sets are uncountable?
GATE 2012 Code A · Q24MCQ1 mark
Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then, is the complement of L also context-free? 3) If L is a regular language, then, is the complement of L also regular? 4) If L is a recursive language, then, is the complement of L also recursive?

Common traps

"CFLs are closed under intersection" is false, but intersection with a regular language is fine.
Context-sensitive languages ARE closed under complement.
RE languages are NOT closed under complement; recursive ones are.