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

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

Check | Ask this |
|---|---|
Termination | Which nonterminal can reach terminals or |
Shape | Are symbols prefixed, suffixed or wrapped? |
Count | What does each production add? |
Order | Is the pattern |
Regularity | Can finite state remember it, or is unbounded equality such as |
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

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.
Keep learning
Grammar Design via Regex: Build a Regular Grammar Step by Step
Turn `(a|b)*abb` into a right-linear grammar through a four-state DFA, then check the construction with complete accepted and rejected traces.
Regex Design & Algebra MCQs: 12 Solved Questions with Explanations
Solve 12 regex design and algebra MCQs with step-by-step reasoning, short counterexamples and a practical method for checking each option.
FA to Regex Conversion MCQs: 12 Solved Questions with Explanations
Solve 12 FA-to-regex conversion MCQs, then use short witness strings, loop analysis and path decomposition to check each answer.
Regex Basics & Definitions MCQs: 12 Solved Questions with Explanations
Solve 12 previous-year regex MCQs step by step. Learn how to read union, concatenation, Kleene star, language powers, anchors, parity, and equivalence.





