High yield ●●●

🌳 Context-Free Grammars & Languages

Why it matters: Ambiguity, normal forms, closure of CFLs and "is it a CFL?" questions are among the most repeated.

Subtopics

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

Formulas

CNF derivation length
a string of length n needs exactly 2n − 1 derivation steps (2n − 1 internal nodes)
GNF derivation length
a string of length n needs exactly n steps
CYK
O(n³ · |G|) time, O(n²) table
CFL pumping lemma
s = uvwxy, |vwx| ≤ p, |vx| ≥ 1, ∀i ≥ 0: uvⁱwxⁱy ∈ L
CFL closure
closed: ∪ · * reverse homomorphism ∩regular. Not closed: ∩, complement, difference
Language of S → aSb | ab
{aⁿbⁿ : n ≥ 1}

What GATE asks from this

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

★★★
Is the grammar ambiguous? / which grammar is unambiguous
Find two parse trees for a string, or check precedence/associativity rules.
★★★
Which languages are context-free
Apply the pumping lemma / closure: aⁿbⁿcⁿ, ww, equal counts, aⁿbᵐcᵏ with conditions.
★★★
CFL closure true/false
Intersection with regular, complement, union, difference.
★★★
Normal forms / simplification
Number of productions or derivation steps in CNF/GNF; remove ε and unit rules.
★★★
Language generated by a grammar
Read the language off a grammar (and what it does NOT generate).

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

Previous year questions

13 real questions from the official GATE CSE papers (2013 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.

13 questions · 0 correct of 0 attempted · marks 0 / 23

Year:
GATE 2025 CS1 · Q19MCQ1 mark
Consider the following context-free grammar G, where S, A, and B are the variables (non-terminals), a and b are the terminal symbols, S is the start variable, and the rules of G are described as: S → aaB | Abb, A → a | aA, B → b | bB. Which ONE of the languages L(G) is accepted by G?
GATE 2025 CS1 · Q45MCQ2 marks
Consider the following two languages over the alphabet {a, b, c}, where m and n are natural numbers. L1 = { ambmcm+n | m, n ≥ 1 } and L2 = { ambncm+n | m, n ≥ 1 }. Which ONE of the following statements is CORRECT?
GATE 2024 CS2 · Q52MSQ2 marks
Consider a context-free grammar G with the following 3 rules. S → aS, S → aSbS, S → c. Let w ∈ L(G). Let na(w), nb(w), nc(w) denote the number of times a, b, c occur in w, respectively. Which of the following statements is/are TRUE?

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

GATE 2023 · Q39MCQ2 marks
Consider the context-free grammar G below: S → aSb | X, X → aX | Xb | a | b, where S and X are non-terminals, and a and b are terminal symbols. The starting non-terminal is S. Which one of the following statements is CORRECT?
GATE 2022 · Q48MSQ2 marks
Consider the following languages: L1 = { ww | w ∈ {a, b}* }, L2 = { anbncm | m, n ≥ 0 }, L3 = { ambncn | m, n ≥ 0 }. Which of the following statements is/are FALSE?

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

GATE 2021 Set 1 · Q1MCQ1 mark
Suppose that L1 is a regular language and L2 is a context-free language. Which one of the following languages is NOT necessarily context-free?
GATE 2019 Set 2 · Q31MCQ2 marks
Which one of the following languages over Σ = {a, b} is NOT context-free?
GATE 2018 · Q35MCQ2 marks
Consider the following languages: I. { ambncpdq | m + p = n + q, where m, n, p, q ≥ 0 }. II. { ambncpdq | m = n and p = q, where m, n, p, q ≥ 0 }. III. { ambncpdq | m = n = p and p ≠ q, where m, n, p, q ≥ 0 }. IV. { ambncpdq | mn = p + q, where m, n, p, q ≥ 0 }. Which of the languages above are context-free?
GATE 2017 Set 1 · Q34MCQ2 marks
If G is a grammar with productions S → SaS | aSb | bSa | SS | ε, where S is the start variable, then which one of the following strings is not generated by G?
GATE 2017 Set 1 · Q37MCQ2 marks
Consider the context-free grammars over the alphabet {a, b, c} given below. S and T are non-terminals. G1: S → aSb | T, T → cT | ε. G2: S → bSa | T, T → cT | ε. The language L(G1) ∩ L(G2) is
GATE 2017 Set 1 · Q38MCQ2 marks
Consider the following languages over the alphabet Σ = {a, b, c}. Let L1 = { anbncm | m, n ≥ 0 } and L2 = { ambncn | m, n ≥ 0 }. Which of the following are context-free languages? I. L1 ∪ L2 II. L1 ∩ L2
GATE 2016 Set 1 · Q16MCQ1 mark
Which of the following languages is generated by the given grammar? S → aS | bS | ε
GATE 2013 Code A · Q32MCQ2 marks
Consider the following languages: L1 = { 0p1q0r | p, q, r ≥ 0 } and L2 = { 0p1q0r | p, q, r ≥ 0, p ≠ r }. Which one of the following statements is FALSE?

Common traps

CFL ∩ CFL need not be CFL, but CFL ∩ regular always is.
The complement of a CFL need not be a CFL (but a DCFL's complement is a DCFL).
Removing ε-productions can change the language only by ε itself.
Ambiguity belongs to the grammar; inherent ambiguity belongs to the language.