Regex Basics & Definitions MCQs: 12 Solved Questions with Explanations

A familiar-looking regex can still describe the wrong language if *, union, concatenation, epsilon, or an anchor is read too quickly.

Attempt these 12 previous-year MCQs before checking each worked answer. Test your choice with an accepted string and a near miss. For a notation refresh, read Regular Expressions and the Pumping Lemma.

1. Regex basics: translate symbols into language operations first

Translate each expression into a language operation before comparing options.

State the language in words, generate short members, and find a separating string. For R={a}, R*={epsilon,a,aa,...}, whereas phi R=phi because no left-hand string exists. The twelve questions here come from GATE, UGC NET, ISRO, IBPS, HPSC, BEL and Coal India papers, so one pass over this notation pays across GATE CS preparation and the PSU exams alike.

2. Regex definitions, operations, and language powers, Questions 1-3

Question 1

Open Question 1 in the question bank

HPSC 2021

Given an alphabet Σ, a regular language is a language which is obtained from the basic languages by using which of the following operations?

A. Union

B. Concatenation

C. Kleene*

D. All of the above

Answer: D. All of the above

Regular languages are closed under all three listed operations. With R={a} and S={b}, they produce {a,b}, {ab}, and R*={epsilon,a,aa,...} respectively. Therefore D includes every permitted construction.

Question 2

Open Question 2 in the question bank

BEL 2023

Which of the following identities of regular expression is NOT correct?

A. ϕ + R = R

B. R* R* = R*

C. ∧R = R

D. ϕR = R

Answer: D. ϕR = R

Here ϕ is the empty language and ∧ is epsilon. For R={a,ab}, ϕ+R=R, ∧R=R, and R*R*=R*. But ϕR has no left-hand string to concatenate, so it equals ϕ, not R. Thus D is the false identity.

Question 3

Open Question 3 in the question bank

Coal India 2017

If L = {ab, c} is a language over the set A = {a, b, c}, then L³ is:

A. {ababc, abcab, abc², cabab, cabc, c²ab, c³}

B. {ababab, ababc, abcab, abc², cabab, c²ab, c³}

C. {ababab, ababc, abcab, abc²abab, cabab, cabc, c²ab, c³}

D. {ababab, ababc, abcab, abc², cabab, cabc, c²ab, c³}

Answer: D. {ababab, ababc, abcab, abc², cabab, cabc, c²ab, c³}

L³=L.L.L. Each position has two choices, so there are 2³=8 concatenations:

ab.ab.ab=ababab, ab.ab.c=ababc, ab.c.ab=abcab, ab.c.c=abc², c.ab.ab=cabab, c.ab.c=cabc, c.c.ab=c²ab, and c.c.c=c³.

The three positions give 2×2×2=8 choices, and none of these strings coincide. Only D contains all eight without an extra or malformed term.

3. Regex cardinality and parity, Questions 4-6

Question 4

Open Question 4 in the question bank

ISRO 2017

For Σ={a,b} the regular expression r = (aa)*(bb)*b denotes:

A. Set of strings with 2 a’s and 2 b’s

B. Set of strings with 2 a’s 2 b’s followed by b

C. Set of strings with 2 a’s followed by b’s which is a multiple of 3

D. Set of strings with even number of a’s followed by odd number of b’s

Answer: D. Set of strings with even number of a’s followed by odd number of b’s

(aa)* contributes 2i a's and (bb)*b contributes 2j+1 b's for i,j>=0. For example, (0,0) gives b, (1,0) gives aab, and (2,1) gives aaaabbb. The fixed order and parities match only D.

Question 5

Open Question 5 in the question bank

GATE 2005

The language {0ⁿ 1ⁿ 2ⁿ | 1 ≤ n ≤ 10⁶} is

A. regular

B. context-free but not regular.

C. context-free but its complement is not context-free.

D. not context-free

Answer: A. regular

The bound gives exactly 10⁶ strings: one for each n from 1 through 10⁶. Every finite language is regular because its members can be written as a finite union of literals. The large bound affects practicality, not regularity, so A is correct.

Question 6

Open Question 6 in the question bank

GATE 2005

Which of the following statements is TRUE about the regular expression 01*0?

A. It represents a finite set of finite strings.

B. It represents an infinite set of finite strings.

C. It represents a finite set of infinite strings.

D. It represents an infinite set of infinite strings

Answer: B. It represents an infinite set of finite strings.

The language is {0 1^k 0 | k>=0}. Values k=0,1,2,3 give 00, 010, 0110, and 01110. Each string is finite, but unbounded k supplies infinitely many distinct strings. Hence B.

4. Regex construction from lexical and substring conditions, Questions 7-9

Question 7

Open Question 7 in the question bank

ISRO 2017

In some programming languages, an identifier is permitted to be a letter followed by any number of letters or digits. If L and D denotes the set of letters and digit respectively. Which of the following expression defines an identifier?

A. (L + D) *

B. (L.D) *

C. L(L + D) *

D. L(L.D) *

Answer: C. L(L + D) *

The first L forces an opening letter; (L+D)* permits any remaining letters or digits, including none. Thus x, x7, and ab2 pass, while 7x fails. A allows a leading digit, and B/D impose letter-digit pairings. Only C matches the rule.

Question 8

Open Question 8 in the question bank

GATE 1997

Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?

A. 0*(1+0)*

B. 0*1010*

C. 0*1*01*

D. 0*(10+1)*

Answer: D. 0*(10+1)*

0* handles the initial zeros. Afterwards, each zero occurs only inside a 10 block, preventing 100. The string 00010110 parses as 000 | 10 | 1 | 10, while 11001 fails because it contains 100. This covers every avoiding string. See the corresponding automaton view in Regex and FA Equivalence MCQs.

Question 9

Open Question 9 in the question bank

IBPS 2025

Which regular expression matches cat and bat, but not at?

A. ^.[cb]at$

B. [cat|bat]

C. ^at$

D. ^[cb]at$

E. .*at$

Answer: D. ^[cb]at$

^ and $ anchor the whole string, while [cb] selects one initial character before at. It accepts cat and bat but rejects at, hat, and scat. A requires an extra character; E accepts any string ending in at. Therefore D.

5. Regex algebra and semantic equivalence, Questions 10-12

Question 10

Open Question 10 in the question bank

UGC NET 2012

Which of the following regular expression identities are true?

A. (r + s)* = r* s*

B. (r + s)* = r* + s*

C. (r + s)* = (r*s*)*

D. r* s* = r* + s*

Answer: C. (r + s)* = (r*s*)*

Any sequence of r- or s-pieces can be grouped into repeated r*s* blocks, and expanding those blocks returns such a sequence. Hence C holds. For r={a}, s={b}, baab parses as b | aab; the witness ba disproves A and B.

Question 11

Open Question 11 in the question bank

UGC NET 2025

If r₁ and r₂ are regular expressions, then which of the following are correct.

A. L(r₁ + r₂) = L(r₁) ∪ L(r₂)

B. L(r₁ . r₂) = L(r₁) L(r₂)

C. L((r₁)) = L(r₁)

D. L(r₁*) = (L(r₁))*

Choose the correct answer from the options given below:

A. A & B only

B. B, C & D only

C. A, C & D only

D. A, B, C & D

Answer: D. A, B, C & D

With r₁=a and r₂=b, the four statements yield {a,b}, {ab}, {a}, and L(a*)=(L(a))*={epsilon,a,aa,...}. These are precisely union, concatenation, grouping, and star semantics. All four statements hold, so the correct choice is A, B, C & D.

Question 12

Open Question 12 in the question bank

UGC NET 2022

Which of the following statements is/are correct about the regular expression?

aa*bb*cc*dd*

A. The language is {a^n b^n c^m d^m | n >= 1, m >= 1} U {a^n b^m c^m d^n | n >= 1, m >= 1}.

B. The given CFG generates the language of the regular expression:

S -> AB | C
A -> aAb | ab
B -> cBd | cd
C -> aCd | aDd
D -> bDc | bc

C. The expression requires equal numbers of a’s, b’s, c’s and d’s.

Choose the correct answer from the options given below:

A. None of A, B and C is correct

B. Only B is correct

C. Both A and B are correct

D. All the three A, B and C are correct

Answer: A. None of A, B and C is correct

aa*bb*cc*dd* means a^i b^j c^k d^l with independent positive counts. The accepted witness aabcccd has counts (2,1,3,1): it fits neither union in A, cannot arise from B's paired-count grammar, and disproves C's equal-count claim. Therefore none is correct.

6. Regex traps: phi versus epsilon, and string length versus language size

Distinguish phi from epsilon, string length from language size, and zero repetitions from one. Convert repeated blocks into count formulas. For substring and identity questions, challenge close options with a near miss or separating witness instead of judging by shape.

7. Regex basics: the short version and the next practice step

Regex questions become mechanical when union, concatenation, zero repetitions, and independent counts stay distinct. Redo Questions 2, 5, 6, and 10, justifying each answer with a definition, boundary case, or separating string.

Continue with GATE Guidance by Sanchit Sir, then practise under test conditions with the GATE Test Series.