Two regexes can look different but denote the same language, while a short expression can hide suffix memory or a trap state. The ten questions below are previous-year problems from GATE, ISRO, UGC NET, BPSC, MPPSC and Coal India papers, on the Theory of Computation ground that GATE Guidance by Sanchit Sir. Commit to an option before reading its explanation.
Use four checks before comparing a regex and an automaton
Run these four checks in order before you answer:
Translate the expression into a plain-language constraint.
Test the shortest strings, including
epsilonwhere relevant.Decide what finite memory a machine must retain.
Count distinguishable states only after identifying that memory.
Equal languages need not have identical syntax. In a complete DFA every transition exists; a partial automaton may omit rejecting transitions.
For a language ending in b, test epsilon, b and ab. For one containing 0011, test 0011, 00011 and 0010. In (a+b)*b(a+b)^4, count exactly four symbols after the fixed b.
Rebuild notation with Regular Expressions and the Pumping Lemma, or revise machine models with Finite Automata: DFA vs NFA.
Equivalence and language-description questions
Q1. Same language, different-looking expressions
GATE, Computer Science, 1998. Solved page.
If the regular set 'A' is represented by A= (01+1)* and the regular set 'B' is represented by B= ((01)* 1*)*, which of the following is true ?
(A) A ⊂ B
(B) B ⊂ A
(C) A and B are incomparable
(D) A = B
Answer: (D) A = B. In A, every token is 01 or 1, so each 0 is followed by 1. Each inner block of B is (01)^k1^m, which preserves that rule.
For both inclusions, each A token is a legal B block. Split each B block into k copies of 01 and m copies of 1 for A. Hence epsilon, 1, 01, 011 are members; 0, 00, 010 are not.
Q2. Read equal exponents literally
Coal India, Computer Science, 2017. Solved page.
Which of the following represents the language over the set A={a,b} consisting of all words beginning with one or more a’s and followed by the same number of b’s?
(A) L={a , ab , ab²,… }
(B) L={aᵐbⁿ: m>0 , n>0 }
(C) L={aᵐbᵐ : m>0 }
(D) L={bᵐabⁿ: m≥0,n≥0}
Answer: (C). It generates ab, aabb, aaabbb. B permits unequal counts such as aab, A fixes one leading a, and D can begin with b.
Yet {a^m b^m : m>0} is not regular. A finite automaton cannot remember unboundedly many a symbols and match the later b count.
Parse the regex before testing strings
Q3. Case-sensitive hexadecimal matching
Indian Space Research Organization, Computer Science, 2025. Solved page.
Which of the following hexadecimal constants match the regular expression given?(0x[0-9A-F]+)
(A) 0x4C5
(B) 0x50b
(C) 04A
(D) 0X
Answer: (A) 0x4C5. Read literal 0x, class [0-9A-F], then + for one or more. B has lowercase b, C lacks 0x, and D has uppercase X plus no class member.
Q4. Membership in a union after a Kleene star
BPSC, Computer Science, 2024. Solved page.
Which of the following strings do not belong to the given regular expression? (a)*(a+cba)
(A) acbca
(B) aaa
(C) acba
(D) More than one of the above
(E) None of the above
Answer: (A) acbca. The branches are a^k a and a^k cba, for k>=0. Thus aaa uses k=2, acba uses k=1, and acbca fits neither. Here + means union, not Q3's one-or-more quantifier.
Q5. Count from the end, not from the start
MPPSC, Computer Science, 2025. Solved page.
Which of the following statements is true for the given Regular Expression? (a+b)*b(a+b)^4
(A) The set of strings containing ab as a substring
(B) The set of strings whose length is divisible by 6
(C) The set of strings having at most one pair of consecutive a’s and at most one pair of consecutive b’s
(D) The set of strings whose 5th symbol from the end is b
Answer: (D). (a+b)^4 consumes four symbols, making the fixed b fifth from the end. (a+b)* permits any earlier prefix.
bbaba splits as epsilon, b, baba; abaaaa as a, b, aaaa. But abaaa starts with the wrong fifth-from-last symbol. Lengths below five fail.
Count states by tracking distinguishable progress
Q6. Exact-length strings need a dead state in a complete DFA
UGC NET, Computer Science, Paper 2 (June), 2012. Solved page.
Consider the regular expression (a + b)(a + b) … (a + b) (n-times). The minimum number of states in finite automaton that recognizes the language represented by this regular expression contains
(A) n states
(B) n + 1 states
(C) n + 2 states
(D) 2n states
Answer: (C) n + 2 states. Exact length n needs progress states 0,1,...,n, or n+1 states, plus a dead state for longer strings.
For n=3, either input advances q0->q1->q2->q3; q3 goes to looping qd. Only q3 accepts. Five states equal 3+2.
Q7. Unary lengths generated by 3 and 5
GATE, Computer Science, 2006. Solved page.
Consider the regular language L = (111 + 11111)*. The minimum number of states in any DFA accepting this languages is:
(A) 3
(B) 5
(C) 8
(D) 9
Answer: (D) 9. Accepted lengths 3i+5j begin 0,3,5,6,8,9,10,...; below 8, 1,2,4,7 fail. Since 8=3+5, 9=3+3+3, 10=5+5, adding 3 covers every later length.
Use exact-length states 0 through 7 and a looping accepting 8+ state. Accept 0,3,5,6,8+. These nine behaviours are distinguishable.
Q8. A partial-automaton convention changes the count
UGC NET, Computer Science, Paper 2 (June), 2019. Solved page.
How many states are there in a minimum state automata equivalent to regular expression given below?Regular expression is 𝑎∗𝑏(𝑎+𝑏)
(A) 1
(B) 2
(C) 3
(D) 4
Answer: (C) 3 under this item's partial-automaton convention. Let q0 loop on a, take q0 --b--> q1, then q1 --a,b--> q2. State q2 accepts without outgoing transitions. A complete DFA adds a rejecting dead state, giving four, as in Q6's convention.
Complement and modular conditions are finite-memory problems
Q9. Complement a fixed-substring DFA without adding states
GATE, Computer Science, Set 3, 2015. Solved page.
Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0, 1}. What is the minimum number of states in a DFA that recognizes L̄ (complement of L)?
(A) 4
(B) 5
(C) 6
(D) 8
Answer: (B) 5. States q0 to q4 track the longest suffix matching a prefix of 0011; q4 means it has appeared.
On 0: q0->q1, q1->q2, q2->q2, q3->q1, q4->q4. On 1: q0->q0, q1->q0, q2->q3, q3->q4, q4->q4. For the complement, accept q0 through q3; reject q4. Only acceptance changes.
Q10. Two modular tests still need only finitely many states
GATE, Computer Science, 2006. Solved page.
For S ∈ (0 + 1) * let d(s) denote the decimal value of s (e.g. d(101) = 5). Let L = {s ∈ (0 + 1)* d(s)mod5 = 2 and d(s)mod7 != 4}. Which one of the following statements is true?
(A) L is recursively enumerable, but not recursive
(B) L is recursive, but not context-free
(C) L is context-free, but not regular
(D) L is regular
Answer: (D) L is regular. Track (r5,r7), updating on bit b to ((2r5+b) mod 5, (2r7+b) mod 7). At most 5*7=35 pairs exist. Accept r5=2, r7!=4.
For 101: (0,0)->(1,1)->(2,2)->(0,5), so decimal 5 fails modulo 5. Decimal 10010 is 18 and also fails since 18 mod 5 = 3. Binary 1100 is 12, with remainders 2 and 5, so it passes.
Audit the answers by the memory each question requires
Question | Answer | Deciding idea |
|---|---|---|
Q1 | D | Equality by two inclusions |
Q2 | C | Same exponent |
Q3 | A | Literal prefix, uppercase class, one-or-more |
Q4 | A | Neither union branch |
Q5 | D | Four trailing symbols |
Q6 | C |
|
Q7 | D | Lengths 0 to 7 plus |
Q8 | C | Three partial-automaton states |
Q9 | B | Five prefix-progress states |
Q10 | D | Remainder pair |
Missing Q1 suggests syntax was compared, not languages. Missing Q3 or Q5 points to poor segmentation; Q6 or Q8 to mixed automaton conventions; Q9 to rebuilding instead of complementing; Q10 to confusing finite modular memory with unbounded counting.
About twenty more previous-year questions on regex and finite-automata equivalence sit on the same solved-question pages linked above. Let your misses decide which to attempt first.
The short version and the next practice step
Equivalent expressions can look different.
Fixed suffix and substring conditions need finite suffix memory.
Unbounded exact equality such as
a^m b^mis not regular.A complete DFA may require a dead state.
Modular conditions remain regular because only finitely many remainders exist.
Redo Q1, Q6, Q9 and Q10 unaided. Write each language constraint, draw its memory states, then check the table. Continue with Finite Automata MCQs for DFA and NFA practice.
Use GATE Guidance by Sanchit Sir for structured Theory of Computation study, then the GATE Test Series for mixed practice.
