Regularity and Identification MCQs: 11 Solved Questions with Explanations

Solve 11 regularity and identification MCQs with concise explanations. Learn when finite memory, closure, pumping, or simplification gives the cleanest proof.

KnowledgeGate Team

Exam prep & CS education

Updated 29 Oct 20268 min read
Regularity and Identification MCQs: 11 Solved Questions with Explanations

Regularity questions rarely ask for a DFA directly. Notation instead hides finite memory, unbounded matching, closure, modulo counting, or fixed bounds. A reliable solution exposes that signal first, then chooses a finite-memory, closure, or pumping argument.

Regularity identification: use a finite-memory checklist

Finite-memory checklist flow from language signal to regularity verdict and proof tool.

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. The language {a^n b^n | n >= 0} must distinguish arbitrarily many n values.

Signal

Likely verdict

Best proof

Fixed bound or finite set

Regular

Enumerate strings or build a DFA

Modulo count

Regular

Track residue states

Equal unbounded counts or an arbitrary copied part

Suspect non-regular

Use regular intersection or pumping

Reversal, union, concatenation, prefix, or suffix of a regular language

Check the construction

Apply the relevant closure property

For DFA state definitions and transition traces, revise DFA Basics MCQs: 12 Solved Questions Explained; that earlier set owns automaton mechanics, while these questions classify languages using finite memory, closure, boundedness, and copying tests. For quantifier-by-quantifier pumping proofs, use Pumping Lemma MCQs: 12 Solved Questions with Explanations; this post stays with the faster identification signals.

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

Three-state residue-cycle DFA accepting strings with 3k+1 b’s, with the four MCQ options contrasted below.

GATE 2014

Which one of the following is TRUE?

  • (a) The language {a^n b^n | n >= 0} is regular.

  • (b) The language {a^n | n is prime} is regular.

  • (c) The language {w | w has 3k+1 b symbols for some k >= 0, over {a,b}} is regular.

  • (d) The language {ww | w is in {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 are non-regular? L1 = {0^m 1^n | 0 <= m <= n <= 10000}; L2 = {w | w reads the same forward and backward}; L3 = {w in {0,1}* | w contains an even number of 0s and an even number of 1s}.

  • (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 L is a regular language over {a,b}, which one of the following languages is NOT regular?

  • (a) L.L^R = {xy | x is in L and y^R is in L}

  • (b) {ww^R | w is in L}

  • (c) Prefix(L) = {x in {a,b}* | there exists y in {a,b}* such that xy is in L}

  • (d) Suffix(L) = {y in {a,b}* | there exists x in {a,b}* such that xy is in L}

Answer: (b). Choose the regular language L = a*b; then {ww^R | w in 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 are regular? L1 = {w x w^R | w and x are over {a,b}*, |w| > 0, and |x| > 0}; L2 = {a^n b^m | m != n and m,n >= 0}; L3 = {a^p b^q c^r | p,q,r >= 0}. Here w^R is the reverse of w.

  • (a) L1 and L3 only

  • (b) L2 only

  • (c) L2 and L3 only

  • (d) L3 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 union 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 L1 = {w in {0,1}* | w has at least as many occurrences of 110 as of 011}. Let L2 = {w in {0,1}* | w has at least as many occurrences of 000 as of 111}. Which one of the following is TRUE?

  • (a) L1 is regular but not L2

  • (b) L2 is regular but not L1

  • (c) Both L1 and L2 are regular

  • (d) Neither L1 nor L2 is 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) {ww^R | w is in {0,1}+}

  • (b) {ww^R x | x and w are in {0,1}+}

  • (c) {w x w^R | x and w are in {0,1}+}

  • (d) {x w w^R | x and w are in {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 these two languages: L1 = {u w w^R v | u, v, and w are nonempty strings over {a,b}}; L2 = {u w w^R v | u, v, and w are nonempty strings over {a,b}, and |u| >= |v|}. Which statement is correct?

  • (a) L1 is regular and L2 is not regular.

  • (b) L1 is not regular and L2 is regular.

  • (c) Both L1 and L2 are regular.

  • (d) Neither L1 nor L2 is regular.

Answer: (a). Here v and v 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 an even number of a's. (B) Strings of a's whose length is a prime number. (C) 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 these languages: L1 = {ww | w is in {a,b}*}; L2 = {ww^R | w is in {a,b}*}; L3 = {0^(2i) | i is an integer}; L4 = {0^(i^2) | i is an integer}. Which of the languages are regular?

  • (a) Only L1 and L2

  • (b) Only L2, L3 and L4

  • (c) Only L3 and L4

  • (d) Only L3

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 these two statements: S1 = {0^(2n) | n >= 1} is a regular language. S2 = {0^m 1^n 0^(m+n) | m >= 1 and n >= 1} is a regular language.

  • (a) Only S1 is correct

  • (b) Only S2 is correct

  • (c) Both S1 and S2 are correct

  • (d) None of S1 and S2 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

Question

Answer

Main clue

1

(a)

DFA definition

2

(c)

Modulo count

3

(d)

Finite bound and parity

4

(b)

Closure counterexample

5

(a)

Existential simplification

6

(a)

Fixed-substring identity

7

(c)

Middle padding

8

(a)

Length comparison

9

(c)

Unary length sets

10

(d)

Copying versus parity

11

(a)

Unbounded sum

The set moves from DFA definitions and residue tests through closure, padding, and unary counting. GATE Guidance by Sanchit Sir provides the wider Theory of Computation 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.