Grammar Design via Regex MCQs: 12 Solved PYQs with Explanations

A grammar question rarely asks only for a definition. It asks you to move between productions, regular expressions, generated strings, productive branches and count invariants, without confusing what a grammar can derive with what it merely resembles. This set gives you exactly 12 solved PYQs. Commit to an option before opening each explanation. KnowledgeGate has over 20 published questions on Grammar Design via Regex, while Semester & College Exam Courses gives you a wider subject-study route. The goal is a method you can reuse under pressure, not option guessing blindly.

Grammar design via regex: a five-check toolkit before the MCQs

For S → aS | bS | ε, a complete trace is S ⇒ aS ⇒ abS ⇒ abbS ⇒ abbaS ⇒ abba. Each step independently selects the next a or b; ε stops at any length. This construction works for any chosen finite string. The language is therefore {a,b}*, including ε, not merely the ordered form a*b*.

Contrast S₁ → aS₁b | ε, which adds matched outer symbols and produces a^n b^n, with S₂ → abS₂ | ε, which repeats one fixed block and produces (ab)*. Review Grammar in Theory of Computation: Types, Trees & CNF if these production shapes need a refresh.

Questions 1-3: read regular grammars as languages and regex

Question 1

(GATE 2016 Set 1)

Which of the following languages is generated by the given grammar?

S → aS | bS | ε

• (a) {aⁿ bᵐ | n,m ≥ 0}

• (b) {w ∈ {a,b}∗ | w has equal number of a’s and b’s }

• (c) {aⁿ | n ≥ 0} ∪ {bⁿ | n ≥ 0} ∪ {aⁿ bⁿ | n ≥ 0}

• (d) {a,b}*

Answer: (d). The abba trace generalises to every finite word: choose either symbol independently, then stop with ε. The other options add absent order or count restrictions.

Question 2

(GATE 2016 Set 2, see the solved page)

Language $L_1$ is defined by the grammar: $S_1 → aS_1b|ε$

Language $L_2$ is defined by the grammar: $S_2 → abS_2|ε$

Consider the following statements:

$P$: $L_1$ is regular

$Q$: $L_2$ 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₁ ⇒ aS₁b ⇒ aaS₁bb ⇒ aaaS₁bbb ⇒ aaabbb, giving nonregular {a^n b^n}. S₂ ⇒ abS₂ ⇒ ababS₂ ⇒ abababS₂ ⇒ ababab, giving regular (ab)*.

Question 3

(GATE 2015 Set 2, see the solved page)

Consider the alphabet ∑ = {0, 1}, the null/empty string 𝜆 and the sets of strings X0, X1, and X2 generated by the corresponding non-terminals of a regular grammar. X0, X1, and X2 are related as follows.

X0 = 1 X1

X1 = 0 X1 + 1 X2

X2 = 0 X1 + {𝜆}

Which one of the following choices precisely represents the strings in X0?

• (a) 10(0* + (10)*)1

• (b) 10(0* + (10)*)*1

• (c) 1(0 + 10)*1

• (d) 10(0 + 10)*1 + 110(0 + 10)*1

Answer: (c). Substitution gives X1 = (0 + 10)X1 + 1; Arden's theorem gives X1 = (0 + 10)*1, hence X0 = 1(0 + 10)*1. Zero repeats gives 11; 0,10 gives 10101.

Questions 4-6: productive branches and grammar class

Question 4

(UGC NET December 2019)

Consider the following grammar:

𝑆→0𝐴∣0𝐵𝐵

𝐴→00𝐴∣𝜆

𝐵→1𝐵∣11𝐶

𝐶→𝐵

Which language does this grammar generate?

• (a) $L((00)^*0+(11)^*1)$

• (b) \(L(0(11)^+1(00)^)\)

• (c) $L((00)^*0)$

• (d) $L(0(11)^*1)$

Answer: (c). B and C never terminate, so discard 0BB. The productive branch S ⇒ 0A ⇒ 0(00)^k gives 0, 000, 00000, ..., or (00)*0.

Question 5

(UGC NET 2013)

Given the following productions of a grammar:

S → aA | aBB

A → aaA | λ

B → bB | bbC

C → B

Which of the following is true?

• (a) The language corresponding to the given grammar is a set of even number of a’s

• (b) The language corresponding to the given grammar is a set of odd number of a’s

• (c) The language corresponding to the given grammar is a set of even number of a’s followed by odd number of b’s

• (d) The language corresponding to the given grammar is a set of odd number of a’s followed by even number of b’s

Answer: (b). B and C cannot terminate. Thus S ⇒ aA ⇒ a(aa)^k has odd length; for k = 2, S ⇒ aA ⇒ aaaA ⇒ aaaaaA ⇒ aaaaa.

Question 6

(UGC NET July 2018)

The set A = { 0n 1n 2n | n=1, 2, 3, ......... } is an example of a grammar that is :

• (a) Context sensitive

• (b) Context free

• (c) Regular

• (d) None of the above

Answer: (a). Read this as {0^n 1^n 2^n}: three ordered blocks with equal counts, a context-sensitive language. For n = 3, 000111222 belongs; 0011222 has counts 2, 2, 3 and fails.

Questions 7-9: turn recursive productions into count and order rules

Question 7

(GATE 2025 Set 1, see the solved page)

Consider the following context-free grammar $G$, where $𝑆, 𝐴,$ 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:

$𝑆 → 𝑎𝑎𝐵 | 𝐴𝑏𝑏$

$𝐴 → 𝑎 | 𝑎𝐴$

$𝐵 → 𝑏 | 𝑏B$

Which ONE of the languages $𝐿(𝐺)$ is accepted by $G$?

• (a) $L(G) = \{ a^{2} b^n \mid n \geq 1 \} \cup \{ a^n b^2 \mid n \geq 1 \}$

• (b) $L(G) = \{ a^n b^{2n} \mid n \geq 1 \} \cup \{ a^{2n} b^n \mid n \geq 1 \}$

• (c) $L(G) = \{ a^n b^n \mid n \geq 1 \}$

• (d) $L(G) = \{ a^{2n} b^{2n} \mid n \geq 1 \}$

Answer: (a). S ⇒ aaB ⇒ aabB ⇒ aabbB ⇒ aabbb proves a²bⁿ. Separately, S ⇒ Abb ⇒ aAbb ⇒ aaAbb ⇒ aaabb proves aⁿb². Union the branches.

Question 8

(GATE 2004)

Consider the following grammar G:

S → bS | aA | b

A → bA | aB

B → bB | aS | a

Let Nₐ(w) and Nᵦ(w) denote the number of a's and b's in a string w respectively. The language L(G) ⊆ {a, b}+ generated by G is

• (a) { w | Nₐ(w) > 3Nᵦ(w)}

• (b) { w | Nᵦ(w) > 3Nᵦ(w)}

• (c) { w | Nₐ(w) = 3k, k ∈ {0, 1, 2, ...}}

• (d) { w | Nᵦ(w) = 3k, k ∈ {0, 1, 2, ...}}

Answer: (c). S ⇒ aA ⇒ aaB ⇒ aaaS, or final B ⇒ a, completes three a symbols. The b loops are unrestricted; S ⇒ b allows k = 0. Option (b) is numerically impossible.

Question 9

(UGC NET June 2019)

Consider the following grammar:

$𝑆→𝑋𝑌 \\ 𝑋→𝑌𝑎𝑌∣𝑎 \ \ and \ \ 𝑌→𝑏𝑏𝑋$

Which of the following statements is/are true about the above grammar?​​​​​​

(a) Strings produced by the grammar can have consecutive three $𝑎’s$.

(b) Every string produced by the grammar have alternate $a$ and $b$.

(c) Every string produced by the grammar have at least two $𝑎’s$.

(d) Every string produced by the grammar have $𝑏’s$ in multiple of 2.

• (a) (a) Only

• (b) (b) and (c) Only

• (c) (d) Only

• (d) (c) and (d) Only

Answer: (d). S ⇒ XY ⇒ aY ⇒ abbX ⇒ abba. Every terminal X has a positive odd a count; every b arrives as bb. Thus (c) and (d) hold, while bb defeats alternation and prevents aaa.

Questions 10-12: membership proofs, derivations and invariants

Question 10

(GATE 2007 Information Technology)

Consider the grammar given below

S → x B | y A

A → x | x S | y A A

B → y | y S | x B B

Consider the following strings.

(i) xxyyx

(ii) xxyyxy

(iii) xyxy

(iv) yxxy

(v) yxx

(vi) xyx

Which of the above strings are generated by the grammar ?

• (a) (i), (ii), and (iii)

• (b) (ii), (v), and (vi)

• (c) (ii), (iii), and (iv)

• (d) (i), (iii), and (iv)

Answer: (c). Equal x,y counts eliminate (i), (v), (vi). Proofs: S ⇒ xB ⇒ xxBB ⇒ xxyB ⇒ xxyyS ⇒ xxyyxB ⇒ xxyyxy; S ⇒ xB ⇒ xyS ⇒ xyxB ⇒ xyxy; S ⇒ yA ⇒ yxS ⇒ yxxB ⇒ yxxy.

Question 11

(GATE 2008 Information Technology)

A CFG G is given with the following productions where S is the start symbol, A is a non-terminal and a and b are terminals.

S→aS∣A

A→aAb∣bAa∣ϵ

Which of the following strings is generated by the grammar above?

• (a) aabbaba

• (b) aabaaba

• (c) abababb

• (d) aabbaab

Answer: (d). S → aS adds leading a; A wraps opposite symbols. S ⇒ aS ⇒ aA ⇒ aaAb ⇒ aabAab ⇒ aabbAaab ⇒ aabbaab, finally using A ⇒ ϵ. The other strings fail the required prefix or wrapping.

Question 12

(GATE 2017 Set 1, see the solved page)

If $G$ is a grammar with productions

$S\rightarrow SaS\mid aSb\mid bSa\mid SS\mid\epsilon$

where $S$ is the start variable, then which one of the following strings is not generated by $G$ ?

• (a) $abab$

• (b) $aaab$

• (c) $abbaa$

• (d) $babba$

Answer: (d). Every production preserves Nₐ ≥ Nᵦ; babba has 2 < 3. The rest are constructible: (ab)(ab), ε·a·aab, and (ab)(ba)·a give abab, aaab, and abbaa.

Grammar design via regex: the short version and next practice step

Redo Questions 2, 3, 7 and 12 in twelve minutes without options. Check for a^n b^n versus (ab)*, X1 = (0 + 10)*1, {a²bⁿ} ∪ {aⁿb²}, and Nₐ = 2 < Nᵦ = 3. Continue with Regex and FA Equivalence MCQs: 10 Solved PYQs. Use Theory Of Computation / Automata Theory for the subject sequence and GATE Guidance by Sanchit Sir for wider preparation.