Context-free grammars sit one level above regular languages, and GATE tests the boundary hard: what a CFG can and cannot generate, which closure properties survive, and where deterministic and nondeterministic pushdown automata part ways. Below are 11 solved MCQs from KnowledgeGate's published question bank, every one a previous-year GATE question with the year marked. Try each before the explanation, which is deliberately short. A note on the deep links: each question here carries a GATE tag inside the course, so we link its exact solved page for the full working. If a result feels unfamiliar, the Context-Free Grammars and Pushdown Automata deep dive and the Theory of Computation learn module build the whole ladder from regular up to recursive.
Context-free grammars and the Chomsky hierarchy
Q1. The C language is (GATE 2002)
(a) a context-free language
(b) a context-sensitive language
(c) a regular language
(d) fully parsable only by a Turing machine
Answer: (b). The syntax of C is largely context-free, which is why parsers use CFGs, but the full set of valid C programs is not. Rules like "an identifier must be declared before use, with a compatible type" depend on context that a CFG cannot enforce. Those context-dependent constraints push the language into the context-sensitive class (see the solved page).
Q2. Let L be the language generated by the grammar S → 0S0 | 00. Which of the following is true? (GATE 2000)
(a) L = 0⁺
(b) L is regular but not 0⁺
(c) L is context free but not regular
(d) L is not context free
Answer: (b). Starting from S, the rule S → 0S0 adds a zero on each side, and S → 00 closes with two zeros, so every string has an even number of zeros and at least two of them. That is the regular language (00)⁺, easily captured by a finite automaton. It is regular but not all of 0⁺, since odd-length strings of zeros are excluded (see the solved page).
Q3. The grammar S → aSa | bSb | a | b over {a, b} generates the set of (GATE 2009)
(a) all palindromes
(b) all odd length palindromes
(c) strings that begin and end with the same symbol
(d) all even length palindromes
Answer: (b). The base rules S → a and S → b produce single symbols, which are palindromes of length one. Each recursive rule wraps the same symbol around both ends, preserving the palindrome property and adding two to the length. Because every string keeps a single symbol at the exact centre, only odd-length palindromes are generated (see the solved page).
Q4. Which one of the following statements is FALSE? (GATE 2004)
(a) There exist context-free languages such that every grammar generating them is ambiguous
(b) An unambiguous CFG always has a unique parse tree for each string it generates
(c) Both deterministic and nondeterministic pushdown automata always accept the same set of languages
(d) A finite set of strings over an alphabet is always a regular language
Answer: (c). Deterministic pushdown automata recognize only the deterministic context-free languages, while nondeterministic PDAs recognize all context-free languages, and the deterministic class is a strict subset. So the two models are not equally powerful, which makes (c) the false statement. The other three are standard true facts, including the existence of inherently ambiguous context-free languages (see the solved page).
Context-free languages and closure
Q5. Context-free languages are closed under (GATE 1999)
(a) union, intersection
(b) union, Kleene closure
(c) intersection, complement
(d) complement, Kleene closure
Answer: (b). Context-free languages are closed under union, concatenation and Kleene closure, because you can combine or repeat their grammars directly. They are not closed under intersection or complement in general, which is why any option pairing those fails. Only union with Kleene closure lists two operations that both preserve context-freeness (see the solved page).
Q6. Which of the following statements is true? (GATE 2001)
(a) If a language is context free it can always be accepted by a deterministic pushdown automaton
(b) The union of two context-free languages is context free
(c) The intersection of two context-free languages is context free
(d) The complement of a context-free language is context free
Answer: (b). Union preserves context-freeness: given two grammars, a new start symbol branching to either one generates the union. Intersection and complement both fail in general, and not every CFL is deterministic, so the other three are false. This is the same closure fact as Q5, now stated as a single true claim (see the solved page).
Q7. Let L be a context-free language and M a regular language. Then the language L ∩ M is (GATE 2006)
(a) always regular
(b) never regular
(c) always a deterministic context-free language
(d) always a context-free language
Answer: (d). Although two context-free languages need not have a context-free intersection, intersecting a CFL with a regular language always stays context free. The construction runs the PDA for L and the finite automaton for M in a product, which is still a PDA. So L ∩ M is always context free, though not necessarily regular or deterministic (see the solved page).
Q8. Let L = L1 ∩ L2, where L1 = { aᵐ bᵐ c aⁿ bⁿ | m, n ≥ 0 } and L2 = { aⁱ bʲ cᵏ | i, j, k ≥ 0 }. Then L is (GATE 2009)
(a) not recursive
(b) regular
(c) context free but not regular
(d) recursively enumerable but not context free
Answer: (c). L1 is context free but not regular, since it matches two separate a to b counts, and L2 is regular. Intersecting a context-free language with a regular one gives a context-free language, so L is context free. It is not regular, because the surviving strings still demand that each a block equal its paired b block (see the solved page).
Pushdown automata and decision properties
Q9. Which of the following problems is undecidable? (GATE 2007)
(a) Membership problem for CFGs
(b) Ambiguity problem for CFGs
(c) Finiteness problem for finite automata
(d) Equivalence problem for finite automata
Answer: (b). Whether a given context-free grammar is ambiguous, meaning some string has two distinct parse trees, has no general decision algorithm. The other three are all decidable: membership by parsing, and finiteness and equivalence for finite automata by standard state-based procedures. So ambiguity of CFGs is the undecidable one (see the solved page).
Q10. Which one of the following problems is undecidable? (GATE 2014)
(a) Deciding if a given context-free grammar is ambiguous
(b) Deciding if a given string is generated by a given CFG
(c) Deciding if the language of a given CFG is empty
(d) Deciding if the language of a given CFG is finite
Answer: (a). The same undecidable problem returns seven years later. There is no algorithm that decides, for every CFG, whether it is ambiguous; the standard proof reduces the Post Correspondence Problem to it. Membership, emptiness and finiteness of a CFG are all decidable by parsing and reachability arguments (see the solved page).
Q11. The language accepted by a pushdown automaton whose stack is limited to 10 items is best described as (GATE 2002)
(a) context-free
(b) regular
(c) deterministic context-free
(d) recursive
Answer: (b). A PDA gets its extra power from an unbounded stack. Cap the stack at 10 items and the number of possible stack contents becomes finite, so pairing the finite control with the finitely many stack configurations yields an ordinary finite automaton. A bounded-stack PDA therefore recognizes only regular languages (see the solved page).
How context-free languages are examined
The pattern is stable across two decades of GATE. The grammar block (Q1 to Q4) tests where a language actually lands in the Chomsky hierarchy and the fact that deterministic PDAs are strictly weaker than nondeterministic ones. The closure block (Q5 to Q8) is almost pure recall backed by one construction: union and Kleene closure survive, intersection and complement do not, and a CFL intersected with a regular language stays context free. The decision block (Q9 to Q11) rewards knowing that CFG ambiguity is undecidable while membership, emptiness and finiteness are not, plus the neat result that a bounded stack collapses a PDA to regular power.
If a question caught you out, the fix is conceptual, not more drilling. Work through the Context-Free Grammars and Pushdown Automata deep dive again, then take the full previous-year sets inside GATE Guidance by Sanchit Sir. Solve, revisit the ones you missed, and return a week later; the second pass is where the closure table and the decidability list become automatic.
