Context-Free Grammar MCQs: 12 Solved CFG Questions

CFG productions can look like a wall, but most options separate once you track one recursive production, one base production and an invariant such as equal counts, parity or palindrome symmetry. The 12 questions below are previous-year problems from GATE, UGC NET and ISRO papers, running from language recognition through ambiguity, CNF, left-recursion removal and grammar reduction. Choose an option and write one short derivation before reading the explanation. The Context-Free Grammars practice set runs to over 60 questions in all, so there is plenty left to attempt after these twelve. Use GATE CS Exam Preparation for a wider study plan.

Read a CFG through its base case, recursive step and invariant

A CFG is G = (V, Σ, P, S), where V contains variables, Σ terminals, P productions and S is the start variable. Find what terminates a derivation, record what one recursive use adds, then test each option with a generated string and a near-miss.

This order matters because one counterexample can reject a tempting option even when several short derivations seem to support its full claimed language.

For S → 0S1 | 01:

S ⇒ 0S1 ⇒ 00S11 ⇒ 000111.

The base adds one 0 and one 1; recursion adds the same pair around it. Thus L = {0^n1^n | n ≥ 1}. The strings 01, 0011 and 000111 are generated. 00111 fails with counts 2 and 3. 0101 fails the required zero-block, then one-block order.

A CFG can generate a regular language, so its form alone does not prove non-regularity. The distinction is developed in Context-Free Grammars and PDAs: CNF, GNF, Pumping Lemma.

CFG MCQs 1-3: regularity and exact language shape

Question 1 (GATE 2007)

Language L₁ is defined by the grammar:

S₁ → aS₁b | ε

Language L₂ is defined by the grammar:

S₂ → abS₂ | ε

Consider the following statements:

P: L₁ is regular

Q: L₂ is regular

Which one of the following is TRUE?

• A. Both P and Q are true

• B. P is true and Q is false

• C. P is false and Q is true

• D. Both P and Q are false

Answer: C. S₁ generates non-regular a^n b^n, including aabb and ε; separated counts must match. S₂ generates regular (ab)^n, including abab. Solution

Question 2 (GATE 2000)

Let L denotes the language generated by the grammar S → 0S0 / 00. Which of the following is true?

• 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. The base has length 2; recursion adds 2. Thus S ⇒ 0S0 ⇒ 0000 and L = (00)^+, which is regular. It excludes the odd-length strings 0 and 000, so it is not 0^+. Solution

Question 3 (GATE 2023)

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?

• A. The language generated by G is (a + b)*

• B. The language generated by G is a*(a + b)b*

• C. The language generated by G is a*b*(a + b)

• D. The language generated by G is not a regular language

Answer: B. X makes a non-empty a*b* string; S → aSb preserves that order. aaa, bbb and aaabb fit, while ba and ε fail. The language is regular despite its CFG. Solution

CFG MCQs 4-6: palindrome grammars and counterexamples

Question 4 (UGC NET 2012)

Which of the following definitions generates the same language as L, where

L = { WWᴿ | W ∈ {a, b}* }

• A. S → aSb | bSa | ε

• B. S → aSa | bSb | ε

• C. S → aSb | bSa | aSa | bSb | ε

• D. S → aSb | bSa | aSa | bSb

Answer: B. WWᴿ is even and palindromic, so matching terminals surround ε: S ⇒ aSa ⇒ abSba ⇒ abba. A forces different ends, C permits ab, and D cannot terminate. Solution

Question 5 (GATE 2009)

S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of

• 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. Each base has length 1; recursion adds two matching symbols. All generated palindromes are odd, as S ⇒ aSa ⇒ abSba ⇒ ababa shows. Even abba is excluded. Solution

Question 6 (GATE 2006)

In the context-free grammar below, S is the start symbol, a and b are terminals, and ϵ denotes the empty string S → aSa | bSb | a | b | ϵ Which of the following strings is NOT generated by the grammar?

• A. aaaa

• B. baba

• C. abba

• D. babaaabab

Answer: B. Bases ϵ, a and b permit both parities. aaaa, abba and babaaabab are palindromes; reverse(baba) = abab. Also, S ⇒ aSa ⇒ aaSaa ⇒ aaaa. Solution

A companion set covers the same area grouped by concept rather than by derivation step: Context-Free Grammar MCQs: 11 Solved GATE Questions repeats three of the questions here and adds eight more, arranged across the Chomsky hierarchy, closure properties and pushdown automata.

CFG MCQs 7-8: nested derivations and ambiguity

Question 7 (GATE 2017)

Consider the following context-free grammar over the alphabet Σ = {a, b, c} with S as the start symbol:

S → abScT | abcT

T → bT | b

Which one of the following represents the language generated by the above grammar?

• A. { (ab)^n (cb)^n | n ≥ 1 }

• B. { (ab)^n cb^m₁ cb^m₂ ... cb^mₙ | n, m₁, m₂, ..., mₙ ≥ 1 }

• C. { (ab)^n (cb^m)^n | m, n ≥ 1 }

• D. { (ab)^n (cb^n)^m | m, n ≥ 1 }

Answer: B. S ⇒ abScT ⇒ abab cT cT. Let the independent T occurrences produce b and bbb: (ab)(ab)(cb)(cbbb) = ababcbcbbb. Their choices need not match. Solution

Question 8 (ISRO 2016)

Consider the following statements about the context free grammar

G = {S-->SS , S-->ab , S-->ba , S-->ε}

I. G is ambiguous.

II. G produces all strings with equal number of a’s and b’s.

III. G can be accepted by a deterministic PDA.

Which combination below expresses all the true statements about G?

• A. I only

• B. I and III only

• C. II and III only

• D. I, II and III

Answer: B. ε has S ⇒ ε and S ⇒ SS ⇒ εS ⇒ ε, proving ambiguity. Regular (ab|ba)* has a deterministic PDA. II fails because equal-count aabb has no valid block split. Solution

CFG MCQ 9: recognizer power and the false statement

Question 9 (GATE 2004)

Which one of the following statements is FALSE?

• A. There exist context-free languages such that all the context-free grammars generating them are ambiguous

• B. An unambiguous context free grammar always has a unique parse tree for each string of the language generated by it.

• C. Both deterministic and non-deterministic pushdown automata always accept the same set of languages

• D. A finite set of string from one alphabet is always a regular language.

Answer: C. Nondeterministic PDAs recognise all CFLs; deterministic PDAs a strict subset. A, B and D hold: inherently ambiguous CFLs exist, unambiguous grammars give one parse tree per string, and finite languages are regular. Solution

If recognizer power is getting mixed up, practise the earlier Finite Automata MCQs: 10 Solved DFA and NFA collection next.

CFG MCQs 10-12: CNF, left-recursion removal and reduction

Question 10 (ISRO 2018)

A CFG(Context Free Grammar) is said to be in Chomsky Normal Form (CNF), if all the productions are of the form A -> BC or A -> a. Let G be a CFG in CNF. To derive a string of terminals of length x, the number of products to be used is

• A. 2x - 1

• B. 2x

• C. 2x + 1

• D. 2ˣ

Answer: A. A CNF tree with x leaves uses x - 1 binary and x terminal productions, totalling 2x - 1. At x = 4, three plus four give seven. Solution

Question 11 (UGC NET 2013)

The equivalent production rules corresponding to the production rules

S → Sα₁ | Sα₂ | β₁ | β₂ is

• A. S → β₁ | β₂
  A → α₁A | α₂A | λ

• B. S → β₁ | β₂ | β₁A | β₂A
  A → α₁A | α₂A

• C. S → β₁ | β₂
  A → α₁A | α₂A

• D. S → β₁ | β₂ | β₁A | β₂A
  A → α₁A | α₂A | λ

Answer: D. The language is one β then zero or more α symbols. D handles zero directly and repetition through nullable A. With α₁=a, α₂=b, β₁=c: S ⇒ cA ⇒ caA ⇒ cabA ⇒ cabbA ⇒ cabb. Solution

Question 12 (UGC NET 2022)

The reduced grammar equivalent to the grammar, whose production rules are given below, is

S→AB∣CA

B→BC∣AB

A→a

C→aB∣b

• A. S→CA,A→a,C→b

• B. S→CA|B,B→BC|B,A→a,C→aB∣b

• C. S→CA|B,B→BC,A→a,C→aB|b

• D. S→AB|AC,B→BC|BA,A→a,C→aB∣b

Answer: A. A and C generate a and b. Every B production keeps a B, so B derives no terminal string: drop it along with S→AB and C→aB. The remainder S→CA, A→a, C→b derives ba. Solution

Diagnose the mistake pattern and choose the next study step

If Questions 1-3 were weak, turn recursion into an invariant. For Questions 4-6, compare end symbols and track parity. For Questions 7-9, write a counterexample before judging a universal claim. For Questions 10-12, separate language recognition from grammar transformation.

Keep this four-line scratch pad:

1. find the base

2. write one recursive expansion

3. name the invariant

4. kill options with one generated string or counterexample

GATE-focused learners can continue with GATE Guidance by Sanchit Sir. For broader semester-level CS, use Zero to Hero, Complete CS Course. Keep deriving once, naming the invariant and testing the options on paper first.