Grammar Design via Regex MCQs: 12 Solved PYQs with Explanations

Solve 12 grammar and regex PYQs by tracing productions, removing dead branches, tracking symbol counts and proving membership with exact derivations.

KnowledgeGate Team

Exam prep & CS education

Updated 29 Oct 20268 min read
Grammar Design via Regex MCQs: 12 Solved PYQs with Explanations

A reliable grammar solve starts with production shape: track termination, symbol order and count changes before choosing a language or regex. Remove branches that cannot terminate, then test a concrete derivation against the candidate. The same discipline handles regular-grammar translations, grammar-class questions, membership proofs and invariants.

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

Derivation loop for S -> aS | bS | epsilon, with the abba trace and comparisons to a^n b^n and (ab)*.

Check

Ask this

Termination

Which nonterminal can reach terminals or epsilon?

Shape

Are symbols prefixed, suffixed or wrapped?

Count

What does each production add?

Order

Is the pattern a*b*, or arbitrary {a,b}*?

Regularity

Can finite state remember it, or is unbounded equality such as a^n b^n required?

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

For state-construction practice, use Regular Grammar and Finite Automata MCQs: 12 Solved Questions with Explanations; this post stays focused on reading productions as regex and proving membership.

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 | epsilon

  • (a) {an bm | n,m >= 0}

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

  • (c) {an | n >= 0} union {bn | n >= 0} union {an bn | n >= 0}

  • (d) {a,b}*

Answer: (d). The abba trace generalises to every finite word: choose either symbol independently, then stop with epsilon. 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|epsilon

Language L_2 is defined by the grammar: S_2 -> abS_2|epsilon

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). S1 => aS1b => aaS1bb => aaaS1bbb => aaabbb, giving nonregular {a^n b^n}. S2 => abS2 => ababS2 => abababS2 => ababab, giving regular (ab)*.

Question 3

(GATE 2015 Set 2, see the solved page)

Consider the alphabet Sigma = {0, 1}, the null/empty string lambda 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 + {lambda}

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

Grammar branch pruning shows 0BB cannot terminate while 0A yields 0, 000, 00000, and (00)*0.

Question 4

(UGC NET December 2019)

Consider the following grammar:

S->0A|0BB

A->00A|lambda

B->1B|11C

C->B

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 | lambda

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 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?

  • (a) L(G) = { a^{2} b^n | n >= 1 } union { a^n b^2 | n >= 1 }

  • (b) L(G) = { a^n b^{2n} | n >= 1 } union { a^{2n} b^n | n >= 1 }

  • (c) L(G) = { a^n b^n | n >= 1 }

  • (d) L(G) = { a^{2n} b^{2n} | n >= 1 }

Answer: (a). S => aaB => aabB => aabbB => aabbb proves a2bn. Separately, S => Abb => aAbb => aaAbb => aaabb proves anb2. Union the branches.

Question 8

(GATE 2004)

Consider the following grammar G:

S -> bS | aA | b

A -> bA | aB

B -> bB | aS | a

Let Na(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 | Na(w) > 3Nβ(w)}

  • (b) { w | N_b(w) > 3N_a(w)}

  • (c) { w | Na(w) = 3k, k in {0, 1, 2, ...}}

  • (d) { w | Nβ(w) = 3k, k in {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:

S->XY ; X->YaY|a and Y->bbX

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

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

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

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

(d) Every string produced by the grammar have b’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|epsilon

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 => epsilon. 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-> SaS| aSb| bSa| SS|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 Na >= Nβ; babba has 2 < 3. The rest are constructible: (ab)(ab), epsilon·a·aab, and (ab)(ba)·a give abab, aaab, and abbaa.

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

Trap

Response

Symbol order

Recheck Questions 1-3.

Nonproductive branch

Delete it in Questions 4-5.

Count obligation

Classify Question 6 only after reading it.

Alternative start branches

Solve them separately in Questions 7-9.

Necessary invariant

Then exhibit derivations in Questions 10-12.

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^2b^n} union {a^n b^2}, and N_a = 2 < N_b = 3. After these production-to-regex derivations, compare expressions with automata in Regex and FA Equivalence MCQs: 10 Solved PYQs. Use Theory of Computation for the subject sequence and GATE Guidance by Sanchit Sir for broader preparation.