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 Φ and the empty string ε; matching by eye is unreliable. These 12 MCQs cover identities, equivalence, parity, forbidden substrings and exact-count languages in GATE CS Exam Preparation. KnowledgeGate has over 60 published questions in this pool. Simplify Φ and ε, 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

Φ has no strings. {ε} has one zero-length string, namely ε. They are not interchangeable.

For R = 0*10*10*, ε 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.

For each item, state the answer and invariant, show an accepted string, then reject the closest rival.

Empty language, empty string and core laws: Questions 1-3

Question 1, GATE 2013

Consider the languages $L_1$ = Φ and $L_2$ = {a }. Which one of the following represents $L_1 L_2^* \cup L_1^*$ ?

• (a) ${є}$

• (b) $Φ$

• (c) $a^*$

• (d) $\{є, a\}$

Answer: (a) \({є}\). Here є denotes ε.

1. L₂* = {ε, a, aa, ...}.

2. L₁L₂* = Φ·L₂* = Φ.

3. L₁* = Φ* = {ε}.

Hence Φ ∪ {ε} = {ε}. 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. $\varphi+\mathrm{L}=\mathrm{L}+\varphi=\mathrm{L}$

B. $\varepsilon \mathrm{L}=\mathrm{L} \varepsilon=\mathrm{L}$

C. $\varphi \mathrm{L}=\mathrm{L} \varphi=\varphi$

D. $\varphi \mathrm{L}=\mathrm{L} \varphi=\mathrm{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 φ adds nothing, {ε} preserves both strings under concatenation, and φ supplies no string to concatenate. Thus A, B and C hold. D fails because φL = φ, 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 ε, r, rr, ... and is closed under concatenation, another star adds nothing. For (c), srrssr = (ε·s)(rr·ss)(r·ε), 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)ⁿx = x(yx)ⁿ. 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 $𝐿_1$ and $𝐿_2$ be languages over $Σ=\{𝑎,𝑏\}$ represented by the regular expressions $(𝑎^∗+𝑏)^∗$ and $(𝑎+𝑏)^∗$ 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 \cap L_2 = \phi$

Answer: (c) \(L_1 = L_2\). Choices from a* or b use only binary symbols, so L₁ ⊆ {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 ε. 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 · ε, with each block shaped 1*0. Option (b) misses 11, and (c) misses ε. Question 6 solved page

Question 7, GATE 1996

Which two of the following four regular expressions are equivalent? (ε denotes the empty string.)

(i) (00)*(ε + 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 {ε, 00, 0000, ...}, the even lengths; (iv) gives {0, 000, 00000, ...}, the odd lengths. Expression (i) appends ε or 0 to an even length, producing {ε, 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. 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\}^* \mid x \text{ ends with 1 and does not contain substring 00 } \}$

• (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 = ε · 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

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.