Regularity and Identification MCQs: 11 Solved Questions with Explanations

Regularity questions rarely ask for a DFA directly. Instead, notation hides finite memory, unbounded matching, closure, modulo counting, or fixed bounds. These 11 solved PYQs pair a repeatable checklist with short explanations of why each answer works.

Regularity identification: use a finite-memory checklist

Simplify existential definitions, then ask whether finite-state memory suffices. Use closure or intersection to isolate difficulty, and pumping only for unbounded matching.

For #b ≡ 1 (mod 3), counts 1, 4, and 7 pass, while 0, 2, 3, 5, and 6 fail. Three states suffice. {a^n b^n | n ≥ 0} must distinguish arbitrarily many n values.

New to state reasoning? Revise DFA Basics MCQs: 12 Solved Questions Explained.

DFA existence, residue counts, and bounded languages

Question 1: DFA definition

Bihar STET 2025

A Language for which DFA exists is a ______

• (a) Regular Language

• (b) Non-Regular Language

• (c) Any language

• (d) Cannot be said

Answer: (a). A language is regular exactly when some DFA recognizes it, so the definition works in both directions. A DFA does not exist for every possible language.

Question 2: modulo counting

GATE 2014

Which one of the following is TRUE?

• (a) The language L={anbn | n≥0} is regular.

• (b) The language L={an | n is prime} is regular.

• (c) The language L={w ∣ w has 3k+1 b’s for some k ∈ N with Σ = {a,b}} is regular.

• (d) The language L={ww ∣ w ∈ Σ∗ with Σ = {0,1}} is regular.

Answer: (c). Counts 1, 4, 7 all leave residue 1 modulo 3, while counts 2 and 3 leave residues 2 and 0. A three-state residue cycle recognizes this language, whereas a^n b^n, prime unary lengths, and exact copying ww require unbounded information.

Question 3: finite bounds versus palindromes and parity

GATE 2008

Which of the following languages is (are) non-regular? L1= {0m1n| 0 ≤ m ≤ n ≤ 10000} L2= {w | w reads the same forward and backward} L3 = {w ∊ {0, 1} * | w contains an even number of 0's and an even number of 1's}

• (a) L2 and L3 only

• (b) L1 and L2 only

• (c) L3 only

• (d) L2 only

Answer: (d). In L1, both m and n range only from 0 through 10000, so the language is finite and regular. L3 needs four parity states, (even, even), (even, odd), (odd, even), and (odd, odd), but an arbitrary binary palindrome needs its unbounded first half remembered.

Closure properties and local-pattern simplification

Question 4: closure constructions

GATE 2019

If 𝐿 is a regular language over Σ = {𝑎, 𝑏}, which one of the following languages is NOT regular ?

• (a) \(L.L^R = \{xy \mid x \in L , y^R \in L\}\)

• (b) \(\{ww^R \mid w \in L \}\)

• (c) \(\text{Prefix } (L) = \{x \in \Sigma^* \mid \exists y \in \Sigma^*\) such that \(𝑥𝑦 ∈ 𝐿 \}\)

• (d) \(\text{Suffix }(L) = \{y \in \Sigma^* \mid \exists x \in \Sigma^*\) such that \(𝑥𝑦 ∈ 𝐿 \}\)

Answer: (b). Choose the regular language L = a*b; then {ww^R | w ∈ L} becomes {a^n b b a^n | n ≥ 0}, which must match two unbounded a blocks. Reversal followed by concatenation preserves (a), while standard finite-automaton constructions preserve prefixes and suffixes.

For a fuller review of those constructions, use Regular Language Properties: Closure and Decision Tests.

Question 5: existential padding and unequal counts

GATE 2015

Which of the following languages is/are regular?$L_1: \left\{ wxw^R \mid w, x \in \{a, b\} ^* \text{ and } |w|, |x| > 0\right\}, w^R \text{ is the reverse of string } w$$L_2: \left\{ a^nb^m \mid m \neq n \text { and } m, n \geq 0 \right\}$$L_3: \left\{ a^pb^qc^r \mid p, q, r \geq 0 \right\}$

• (a) \(L_1\) and \(L_3\) only

• (b) \(L_2\) only

• (c) \(L_2\) and \(L_3\) only

• (d) \(L_3\) only

Answer: (a). Choosing |w| = 1 shows that L1 is exactly the length-at-least-3 strings whose first and last symbols match, described by a(a+b)+a ∪ b(a+b)+b; L3 is simply a*b*c*. If L2 were regular, subtracting it from regular a*b* would make {a^n b^n} regular, a contradiction.

Question 6: comparing counts of fixed substrings

GATE 2014

Let $L_1 = \{ w \in \{0,1\}^* | w$ has at least as many occurrences of (110)’s as (011)’s}. Let $L_2 = \{ w \in \{0,1\}^* | w$ has at least as many occurrences of (000)’s as (111)’s}. Which one of the following is TRUE?

• (a) \(L_1\) is regular but not \(L_2\)

• (b) \(L_2\) is regular but not \(L_1\)

• (c) Both \(L_1\) and \(L_2\) are regular

• (d) Neither \(L_1\) nor \(L_2\) are regular

Answer: (a). In 11011, 110 and 011 each occur once, and the identity #110 - #011 = s1s2 - s(n-1)s(n) means a DFA needs only the first two and latest two bits. For L2, let the pumping length be p: 1^(2p)0^(2p) has 2p-2 occurrences of each triple, but pumping up a nonempty block from the first p ones raises #111 while #000 remains 2p-2, so the pumped string leaves L2.

Reverse, copy, and padded-string traps

Question 7: a reversible middle block

GATE 2007

Which of the following languages is regular?

• (a) {wwR|w ∈ {0,1}+}

• (b) {wwRx|x,w∈{0,1}+}

• (c) {wxwR|x,w∈{0,1}+}

• (d) {xwwR|x,w∈{0,1}+}

Answer: (c). Choose w as the first symbol and let nonempty x absorb the middle, so (c) is exactly the strings of length at least 3 whose first and last symbols match. In the other placements, the forced mirrored block reaches an edge and retains an unbounded comparison.

Question 8: padded ww^R with a length condition

UGC NET 2016

Given the following two languages :$L_{1} = \{uww^{R} ν | u, v, w \in (a, b)^{+}\} \\ L_{2} = \{uww^{R} ν | u, ν, w \in (a, b)^{+} , |u| \geq |ν|\}$Which of the following is correct ?

• (a) 𝐿1 is regular language and 𝐿2 is not regular language.

• (b) 𝐿1 is not regular language and 𝐿2 is regular language.

• (c) Both 𝐿1 and 𝐿2 are regular languages.

• (d) Both 𝐿1 and 𝐿2 are not regular languages.

Answer: (a). Here v and ν denote the same final nonempty block; in L1, taking |w| = 1 means finding an internal aa or bb with a nonempty prefix and suffix. Intersecting L2 with regular (ba)+bb(ab)+ gives {(ba)^r bb (ab)^s | r ≥ s ≥ 1}; pumping down the first block in (ba)^p bb (ab)^p breaks the form or leaves fewer left pairs, proving non-regularity.

Unary lengths, primes, squares, and exact copies

Question 9: prime and square unary lengths

UGC NET 2017

Which of the following are not regular ?(A) Strings of even number of a’s.(B) Strings of a’s, whose length is a prime number.(C) Set of all palindromes made up of a’s and b’s.(D) Strings of a’s whose length is a perfect square.

• (a) (A) and (B) only

• (b) (A), (B) and (C) only

• (c) (B), (C) and (D) only

• (d) (B) and (D) only

Answer: (c). Even lengths 0, 2, 4, 6 repeat modulo 2 and are regular. Prime lengths 2, 3, 5, 7 and square lengths 1, 4, 9, 16 do not settle into a fixed finite cycle, while binary palindromes require an arbitrary first half to be remembered.

Question 10: copying versus even and square lengths

GATE 2001

Consider the following languagesL₁ = { ww | w ∈ {a, b}* }L₂ = { wwᴿ | w ∈ {a, b}*, wᴿ is the reverse of w }L₃ = { 0²ⁱ | i is an integer }L₄ = { 0ⁱ² | i is an integer }Which of the languages are regular?

• (a) Only L₁ and L₂

• (b) Only L₂, L₃ and L₄

• (c) Only L₃ and L₄

• (d) Only L₃

Answer: (d). Here L3 = {0^(2i)} and L4 = {0^(i^2)}. At i = 0, 1, 2, 3, L3 gives lengths 0, 2, 4, 6, a parity cycle, while exact copies ww, even palindromes ww^R, and square lengths 0, 1, 4, 9, 16 need more than fixed residue memory.

Question 11: two unary and counting statements

GATE 2001

Consider the following 2 statementsS₁: { 0²ⁿ | n ≥ 1 } is a regular languageS₂: { 0ᵐ 1ⁿ 0ᵐ⁺ⁿ | m ≥ 1 and n ≥ 1 } is a regular language

• (a) Only S₁ is correct

• (b) Only S₂ is correct

• (c) Both S₁ and S₂ are correct

• (d) None of S₁ and S₂ is correct

Answer: (a). Interpreting S1 as positive even zero-lengths gives 2, 4, 6, ..., recognized by a three-state DFA with start, odd, and positive-even states. In S2, m = 2 and n = 3 produce 00 111 00000; a recognizer would need the unbounded sum m + n = 5 for the final block, so the language is not regular.

Regularity questions: match each clue to the proof tool

Questions 1 to 3 test DFA signatures, 4 to 6 closure, 7 and 8 padding, and 9 to 11 unary counting. GATE Guidance by Sanchit Sir provides the wider route.

Regularity and identification MCQs: the short version and next step

Keep four rules: finite bounds are regular, modulo cycles are regular, unbounded equality or copying is non-regular, and existential padding needs simplification. Match each clue to the lightest proof.

Continue with Theory Of Computation / Automata Theory for the concept sequence. For broader revision, use CS Fundamentals for Exams & Placements, then explain the answers without the table.