These 12 published questions cover membership, loops, parity, equivalent expressions, path decomposition and multi-NFA matching. Choose an option before reading its explanation. For a broader route, see the GATE CS Exam Preparation Courses & Test Series. Questions 2, 11 and 12 lack separate solved pages; use the FA to Regex Conversion PYQ Questions hub for further practice.
1. FA to regex conversion: the three checks to use before the MCQs
First describe the accepted language. Mark loops and complete start-to-final paths. Test each candidate on one accepted and one rejected string. If inspection gets messy, use state elimination or Arden's theorem.
Use states S (start), A and F (only final): S --0--> S, S --1--> A, A --0--> A, A --1--> F, F --0--> F; F has no 1 transition.
The loops allow zeros before, between and after the two required 1s: R_S = ε + R_S0 = 0*, R_A = R_S1 + R_A0 = 0*10*, and R_F = R_A1 + R_F0 = 0*10*10*. Thus exactly two 1s are accepted. Witnesses: 11, 01010, 10010; counterexamples: ε, 1, 111, 1101.
2. FA to regex MCQs 1-3: membership and whole-language recognition
Question 1, GATE 1998
The string 1101 does not belong to the set represented by
(a)
110*(0 + 1)(b)
1(0 + 1)*101(c)
(10)*(01)*(00 + 11)*(d)
(00 + (11)*01)*
Answer: (c) (10)*(01)*(00 + 11)*. Options (a), (b) and (d) generate 1101 using 0, ε and (11)01, respectively. No split allowed by (c) does. GATE 1998 solution.
Question 2
Consider the following NFA:
!NFA supplied with bank question 29021
The regular expression corresponding to above NFA is
(a)
(a+b)*(b)
(a*b)*(c)
aa*bb*(d)
a+b+
Answer: (a) (a+b)*. Repeatable a*b* blocks give (a*b*)*, equal to every string over a,b. Option (b) cannot generate a; (c) and (d) require both symbols.
Question 3, ISRO 2023
Consider the NFA with epsilon-transitions below, which is meant to accept strings corresponding to a lexical token id. Here the token digit corresponds to the extended regular expression [0-9] and letter corresponds to [a−zA−Z]. In the diagram, a small incoming edge indicates a start state while a double circle indicates a final state.
!NFA for the lexical token id in bank question 57660
Which of the following extended regular expressions corresponds to the token id?
(a)
letter (letter | digit)*(b)
(letter I digit)* letter(c)
(letter | digit)*(d)
letter (letter* | digit*)
Answer: (a) letter (letter | digit)*. The first symbol must be a letter; later branches repeat either type. Thus x, x7 and x7B2 pass, while 7x and ε fail. Option (d) blocks free alternation. ISRO 2023 solution.
3. FA to regex MCQs 4-6: prefixes, loops and return paths
Question 4, GATE 2006, Information Technology
Which regular expression best describes the language accepted by the non-deterministic automaton below?
!Nondeterministic automaton supplied with bank question 11049
(a)
(a + b)* a(a + b)b(b)
(abb)*(c)
(a + b)* a(a + b)* b(a + b)*(d)
(a + b)*
Answer: (a) (a + b)* a(a + b)b. After any prefix, acceptance needs a, either symbol, then b. Thus aab and bbabb pass; ab, abba and bbb fail. Option (c) allows a suffix. GATE 2006 solution.
Question 5, MPPSC 2025, Computer Science
Which of the following is equal Regular Expression for the given Finite Automata?
!Finite automaton supplied with bank question 63275
(a)
(aa + bb) a* (ab + ba)(b)
(aa + bb) (a + b)* (aa + bb)(c)
a* (a + b)* ab(d)
bb(a + b)* aa
Answer: (b) (aa + bb) (a + b)* (aa + bb). Entry and exit are each aa or bb; the middle is arbitrary. The strings aaaa, aabbaa and bbbb fit. Option (d) keeps one pairing. MPPSC solution.
Question 6, GATE 2023
Consider the Deterministic Finite-state Automaton (DFA) A shown below. The DFA runs on the alphabet {0, 1}, and has the set of states {s, p, q, r}, with s being the start state and p being the only final state.
!Four-state DFA supplied with bank question 2288
Which one of the following regular expressions correctly describes the language accepted by A?
(a)
1(0∗11)∗(b)
0(0 + 1)∗(c)
1(0 + 11)∗(d)
1(110∗)∗
Answer: (c) 1(0 + 11)∗. The first 1 accepts. The reusable return units are 0 and 11. Therefore 1, 10, 111 and 10011 pass; ε, 0 and 11 fail. GATE 2023 solution.
4. FA to regex MCQs 7-9: equivalence, parity and false statements
Question 7, GATE 2013
Consider the DFA given below:
!DFA supplied with bank question 3732
Which of the following are FALSE?
Complement of L(A) is context-free.
L(A) = L((11*0+0)(0 + 1)*0*1*)
For the language accepted by A, A is the minimal DFA.
A accepts all strings over {0, 1} of length at least 2.
(a)
1 and 3 only(b)
2 and 4 only(c)
2 and 3 only(d)
3 and 4 only
Answer: (d) 3 and 4 only. The language is binary strings containing 0. Its complement 1* is context-free, and statement 2 is equivalent. Equivalent non-final states make 3 false; 11 disproves 4. GATE 2013 solution.
Question 8, GATE 2014, Set 1
Which of the regular expressions given below represent the following DFA?
!DFA supplied with bank question 3540
I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1
(a)
I and II only(b)
I and III only(c)
II and III only(d)
I, II, and III
Answer: (b) I and III only. Acceptance means a non-empty string ending in 1. III says this directly; I partitions such strings into initial zeros and later runs ending in 1. II misses 00101. GATE 2014 solution.
Question 9, GATE 2024, Set 2
Which one of the following regular expressions is equivalent to the language accepted by the DFA given below?
!DFA supplied with bank question 2166
(a)
0∗1(0 + 10∗1)∗(b)
0∗ (10∗11)∗0∗(c)
0∗1(010∗1)∗0∗(d)
0(1 + 0∗10∗1)∗0∗
Answer: (a) 0∗1(0 + 10∗1)∗. The prefix creates odd 1 parity; each unit adds zero or two 1s. Thus 1, 00100 and 10101 pass; ε, 11 and 101 fail. GATE 2024 solution.
5. FA to regex MCQs 10-12: round trips and multi-path decomposition
Question 10, GATE 2022
Which one of the following regular expressions correctly represents the language of the finite automaton given below?
!Finite automaton supplied with bank question 2351
(a)
ab* bab* + ba* aba*(b)
(ab*b)* ab* - (ba*a)* ba*(c)
(ab*b + ba*a)* + (a* + b*)(d)
(ba*a + ab*b)* (ab* + ba*)
Answer: (d) (ba*a + ab*b)* (ab* + ba*). Return trips are ba*a or ab*b; the final segment is ab* or ba*. Option (b) subtracts languages; (c) accepts ε from a non-final start. GATE 2022 solution.
Question 11
Consider the following Finite automata:
!Finite automaton supplied with bank question 12536
The regular expression for the above FA is
(a)
11*00*1(00*1+11*00*1)*(b)
11*00*1(0+1)*(c)
11*00*1(01+101)*(d)
none of these
Answer: (a) 11*00*1(00*1+11*00*1)*. The first path is 11*00*1; return cycles are 00*1 and 11*00*1. Both 101 and 101001 fit. Option (b) admits 1010; (c) misses 101001.
Question 12, GATE 2008
Match the following NFAs with the regular expressions they correspond to:
!Four NFAs and four regular expressions supplied with bank question 30139
(a)
P-2, Q-1, R-3, S-4(b)
P-1, Q-3, R-2, S-4(c)
P-1, Q-2, R-3, S-4(d)
P-3, Q-2, R-1, S-4
Answer: (c) P-1, Q-2, R-3, S-4. Match suffixes: P ends in 0, Q in 01*, R in 1, and S in 10*. The map is P: ε + 0(10*1 + 00)*0; Q: ε + 0(01*1 + 00)*01*; R: ε + 0(10*1 + 10)*1; S: ε + 0(10*1 + 10)*10*.
6. The conversion traps these 12 questions expose
Trap | Questions that expose it |
|---|---|
Testing only one example | Q1 |
Forgetting that | Q2 and Q12 |
Confusing arbitrary prefix with arbitrary suffix | Q4 |
Dropping an entry or exit branch | Q5 |
Treating a one-way path as repeatable | Q6 and Q11 |
Matching syntax instead of the language invariant | Q7 to Q10 |
In a timed solve, mark start/final states and ε acceptance, then list loops and return cycles. Build prefix(loop)*suffix; test the shortest accepted and rejected strings. Continue with Theory of Computation MCQs. Regular expressions also support lexical analysis, covered in Compiler Design MCQs.
7. FA to regex conversion: the next practice step
Redo Questions 1, 6, 8, 10 and 12 without the explanations, allowing two minutes each. Use GATE Guidance by Sanchit Sir for a sequenced Theory of Computation route. For mixed-subject practice, use the GATE Test Series.
Describe the language first, convert reusable paths, and eliminate look-alike expressions with short witness strings.
