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

Updated 29 Oct 20268 min read
Regex Design & Algebra MCQs: 12 Solved Questions with Explanations

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

Comparison of Phi and {epsilon}, with accepted and rejected witnesses for R = 0*10*10*.

Law

With L = {a, bb}

Phi + L = L

Phi + L = {a, bb}

PhiL = LPhi = Phi

PhiL = Phi

epsilonL = Lepsilon = L

epsilonL = {a, bb}

Phi* = {epsilon}

Phi* = {epsilon}

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.

  1. L_2* = {epsilon, a, aa, ...}.

  2. L_1L_2* = Phi.L_2* = Phi.

  3. 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

Even-parity regex built from a zero prefix and repeated two-1 blocks, with example decomposition.

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

Phi versus epsilon

No strings versus one zero-length string

Question 1 gives {epsilon}

Mandatory symbol outside star

It creates a minimum count

Question 11: 00100010 has exactly two 1s

(0+1)* around two zeros

It means at least two, not exactly two

Question 12 accepts 0101

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.