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.
KnowledgeGate Team
Exam prep & CS education

Regex options often differ by one star, one mandatory symbol, or a swap between the empty language Phi and the empty string epsilon; matching by eye is unreliable. These 12 MCQs cover identities, equivalence, parity, forbidden substrings and exact-count languages in GATE CS Exam Preparation. The practice pool contains over 60 questions. A reliable check is to simplify Phi and epsilon, expand the first three strings, state one invariant, then seek the shortest counterexample to each rival. Eleven questions link to individual solved pages; Question 4 uses the shared Regex Design & Algebra practice hub.
Regex design and algebra: the four-line scratchpad

Law | With |
|---|---|
|
|
|
|
|
|
|
|
Phi has no strings. {epsilon} has one zero-length string, namely epsilon. They are not interchangeable.
For R = 0*10*10*, epsilon and 000 fail because two 1s are mandatory. 11, 101 and 0010010 pass with exactly two 1s; 111 fails with three. A short witness often settles equivalence.
Test each option by stating its invariant, showing an accepted string, and rejecting the closest rival.
Empty language, empty string and core laws: Questions 1-3
Question 1, GATE 2013
Consider the languages L_1 = Phi and L_2 = {a }. Which one of the following represents L_1 L_2^* union L_1^* ?
(a) {epsilon}
(b) Phi
(c) a^*
(d) {epsilon, a}
Answer: (a) {epsilon}. Here epsilon denotes epsilon.
L_2* = {epsilon, a, aa, ...}.L_1L_2* = Phi.L_2* = Phi.L_1* = Phi* = {epsilon}.
Hence Phi union {epsilon} = {epsilon}. Option (b) forgets that star includes zero repetitions. The string a, generated by neither term, rejects (c) and (d). Question 1 solved page
Question 2, UGC NET December 2022
Which of the following are correct on regular expressions?
A. phi + L = L + phi = L
B. epsilon L = L epsilon = L
C. phi L = L phi = phi
D. phi L = L phi = L
Choose the correct answer from the options given below:
(a) A, B and D only
(b) A, B and C only
(c) B and D only
(d) A and D only
Answer: (b) A, B and C only. For L = {a, bb}, union with phi adds nothing, {epsilon} preserves both strings under concatenation, and phi supplies no string to concatenate. Thus A, B and C hold. D fails because phiL = phi, not {a, bb}. Question 2 solved page
Question 3, UGC NET August 2016
Consider the following identities for regular expressions :
(a) (r + s)* = (s + r)*
(b) (r*)* = r*
(c) (r* s*)* = (r + s)*
Which of the above identities are true ?
(a) (a) and (b) only
(b) (b) and (c) only
(c) (c) and (a) only
(d) (a), (b) and (c)
Answer: (d) (a), (b) and (c). Commutative union proves (a). Since r* contains epsilon, r, rr, ... and is closed under concatenation, another star adds nothing. For (c), srrssr = (epsilon.s)(rr.ss)(r.epsilon), three r*s* blocks. Conversely, every such block is a sequence of r and s. Question 3 solved page
Moving factors through a star and simplifying nested choices: Questions 4-5
Question 4
Which of the following is correct
(a) (xx)y = x(xy)
(b) (xy)x = x(yx)
(c) x(xy)* = (xx)*y
(d) (xy)* = (yx)*
Answer: (b) (xy)*x = x(yx)*. At zero, one and two repetitions, both sides give x, xyx and xyxyx. Generally, (xy)^nx = x(yx)^n. Option (d) fails for x = a, y = b: the left contains ab, while the right has ba at length two.
Question 5, UGC NET June 2020
Let L1 and L2 be languages over Sigma = {a, b}, represented by the regular expressions (a* + b)* and (a + b)* respectively.
Which of the following is true with respect to the two languages?
(a) L_1 subset L_2
(b) L_2 subset L_1
(c) L_1 = L_2
(d) L_1 intersection L_2 = phi
Answer: (c) L_1 = L_2. Choices from a* or b use only binary symbols, so L_1 subset of {a,b}*. Conversely, baababb = b . aa . b . a . b . b: every a-run is in a*, and every b is a singleton. This works for all binary words, including epsilon. Question 5 solved page
Regex equivalence by decomposition and counterexample: Questions 6-8
Question 6, GATE 2003
The regular expression 0*(10*)* denotes the same set as
(a) (1*0)1
(b) 0 + (0 + 10)*
(c) (0 + 1)* 10(0 + 1)*
(d) none of these
Answer: (a) (1*0)*1*. Both sides generate every binary string. The stem factors 00110100 as 00 . 1 . 10 . 100; option (a) uses 0 . 0 . 110 . 10 . 0 . epsilon, with each block shaped 1*0. Option (b) misses 11, and (c) misses epsilon. Question 6 solved page
Question 7, GATE 1996
Which two of the following four regular expressions are equivalent? (epsilon denotes the empty string.)
(i) (00)*(epsilon + 0)
(ii) (00)*
(iii) 0*
(iv) 0(00)*
(a) (i) and (ii)
(b) (ii) and (iii)
(c) (i) and (iii)
(d) (iii) and (iv)
Answer: (c) (i) and (iii). Expression (ii) gives {epsilon, 00, 0000, ...}, the even lengths; (iv) gives {0, 000, 00000, ...}, the odd lengths. Expression (i) appends epsilon or 0 to an even length, producing {epsilon, 0, 00, 000, ...} = 0*, exactly (iii). Question 7 solved page
Question 8, GATE 2004, Information Technology
Which one of the following regular expressions is NOT equivalent to the regular expression (a + b + c) *?
(a) (a* + b* + c*)*
(b) (a*b*c*)*
(c) ((ab)* + c*)*
(d) (a*b* + c*)*
Answer: (c) ((ab)* + c*)*. Options (a), (b) and (d) each generate a, b and c; the outer star joins them in any order, reaching {a,b,c}*. Option (c) has powers of ab and c, but no bare a or b. The string a is decisive. Question 8 solved page. The linked sibling owns regex-to-FA equivalence; this post owns algebraic rewrites and witness strings. Next, try Regex and FA Equivalence MCQs: 10 Solved PYQs.
Designing a regex for even parity: Question 9

Question 9, GATE 2010
Let L = { w in (0 + 1)* | w has an even number of 1s }. That is, L is the set of all bit strings with an even number of 1s. Which one of the following regular expressions represents L?
(a) (0*10*1)*
(b) 0*(10*10*)*
(c) 0*(10*1)*0
(d) 0*(10*1)10
Answer: (b) 0*(10*10*)*. Each block contributes two 1s; 0* contributes none. The string 000 uses the leading prefix and zero blocks. Also, 0010010110 = 00 . 10010 . 110, with two 10*10* blocks. Option (a) misses 110; (d) adds a final mandatory 1, making the count odd. Question 9 solved page
Ends-with and forbidden-substring design: Question 10
Question 10, UGC NET June 2015
The regular expression corresponding to the language L, where L = { x in {0,1}* | x ends with 1 and does not contain substring 00 }, is:
(a) (1+01)* (10+01)
(b) (1+01)* 01
(c) (1+01)* (1+01)
(d) (10+01)* 01
Answer: (c) (1+01)* (1+01). This is one or more 1 or 01 tokens. Every word ends in 1; each 0 is followed by 1, preventing 00. Conversely, 1 = 1, 101 = 1.01, and 01011 = 01.01.1. Option (b) misses 1; (a) accepts 10, which ends in 0. Question 10 solved page
Exact count versus at least count: Questions 11-12
Question 11, GATE 2008, Information Technology
Which of the following regular expressions describes the language over {0, 1} consisting of strings that contain exactly two 1's?
(a) (0 + 1) * 11(0 + 1) *
(b) 0 * 110 *
(c) 0 * 10 * 10 *
(d) (0 + 1) * 1(0 + 1) * 1 (0 + 1) *
Answer: (c) 0 * 10 * 10 *. It has two mandatory 1s, and every starred region contains only 0: 00100010 = 00 . 1 . 000 . 1 . 0. Option (b) requires adjacent 1s. Options (a) and (d) permit extras in their (0+1)* regions, meaning at least two. Question 11 solved page
Question 12, GATE 2009
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)0(0+1) ?
(a) The set of all strings containing the substring 00.
(b) The set of all strings containing at most two 0’s.
(c) The set of all strings containing at least two 0’s.
(d) The set of all strings that begin and end with either 0 or 1.
Answer: (c) The set of all strings containing at least two 0’s. Two explicit 0s are required; the starred regions add arbitrary context. The factorisation 0101 = epsilon . 0 . 1 . 0 . 1 disproves (a). The string 111 fails, while 000 passes because a starred region adds a zero, disproving (b). Question 12 solved page
Regex MCQ trap table, score check and next step
Trap | Reliable check | Worked reminder |
|---|---|---|
| No strings versus one zero-length string | Question 1 gives |
Mandatory symbol outside star | It creates a minimum count | Question 11: |
| It means at least two, not exactly two | Question 12 accepts |
Claimed equivalence | Prove both containments; one counterexample disproves it | Test the shortest strings first |
With 10-12 correct, move to mixed equivalence sets. With 7-9, redo Questions 1, 3, 7 and 9. With 0-6, rebuild the laws and generate three strings per regex. Then study Regular Language Properties: Closure and Decision Tests.
Connect design to proofs with Regular Expressions and Pumping Lemma: Worked Proof. Use Theory Of Computation / Automata Theory for the focused path, or GATE Guidance by Sanchit Sir for wider preparation.
Keep learning
Regex Design and Algebra Explained: Identities, Arden's Theorem, and Worked Examples
Build regular expressions from language constraints, simplify them with safe identities, prove the result, and solve a recursive equation with Arden's theorem.
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.
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.





