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

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

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

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
(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
(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
(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
(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
(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
(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
(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.
Keep learning
Regularity Identification in Automata Theory: DFA/NFA Tests and Worked Proofs
Learn how to classify languages by the memory they need, construct a product DFA, and prove a genuinely non-regular language with pumping and Myhill-Nerode.
CFL Identification MCQs: 12 Solved Questions with Explanations
Solve 12 CFL identification MCQs in sequence, from basic PDA scope to intersections, copy languages and multi-constraint classifications. Each answer includes a fresh reason you can reuse under exam pressure.
CFL Identification: Decision Rules, Worked Examples and Exam Traps
Learn a repeatable way to classify context-free languages, from constructive grammar and stack evidence to safe closure arguments and a complete non-CFL proof.
Mealy Machine MCQs: 11 Solved Questions with State-Trace Explanations
Solve 11 Mealy machine MCQs using state tables, edge-output traces and fresh explanations. Each answer shows how to eliminate plausible options.





