Finite Automata
Finite Automata Tricky GATE MCQs with Solutions
Q1. Which of the following is not true for Deterministic Finite Automata (DFA)?
A) Every DFA has exactly one transition per symbol from each state.
B) DFA can recognize all regular languages.
C) DFA can have ε-transitions.
D) DFA can have multiple final states.
Answer: C
Explanation: DFA does not allow ε-transitions. Only NFA and ε-NFA can have them.
Q2. The minimum number of states required to accept all binary strings divisible by 5 is:
A) 4
B) 5
C) 6
D) 3
Answer: B
Explanation: To recognize divisibility by 5, DFA must track remainders 0–4 ⇒ 5 states.
Q3. Which of the following statements is true?
A) Every NFA has a unique equivalent DFA.
B) Every NFA can be converted into a DFA.
C) Some NFAs cannot be converted into a DFA.
D) DFA and NFA accept different language classes.
Answer: B
Explanation: NFAs and DFAs recognize the same class — regular languages.
Q4. Which of the following is false about ε-NFA?
A) ε-transitions do not consume input.
B) ε-NFA can be converted into NFA.
C) ε-NFA accepts more languages than NFA.
D) ε-NFA can accept a string even without reading any symbol.
Answer: C
Explanation: ε-NFA, NFA, and DFA all accept the same class of languages.
Q5. In a DFA, how many transitions exist from a state if the alphabet has 3 symbols?
A) 1
B) 2
C) 3
D) Depends on input string
Answer: C
Explanation: DFA must have exactly one outgoing transition per alphabet symbol.
Q6. Which of the following languages is not regular?
A) Set of strings with even number of a’s
B) Set of strings where number of a’s = number of b’s
C) Set of strings ending with ‘01’
D) Set of strings having substring ‘00’
Answer: B
Explanation: Equal number of a’s and b’s requires counting — not possible in FA.
Q7. The number of states in a minimal DFA for binary strings containing substring “11” is:
A) 2
B) 3
C) 4
D) 5
Answer: B
Explanation: DFA needs states to represent: no ‘1’ seen, one ‘1’ seen, “11” found.
Q8. For an NFA with n states, what is the maximum number of states possible in its equivalent DFA?
A) n
B) 2ⁿ
C) n²
D) 2n
Answer: B
Explanation: The subset construction can produce up to 2ⁿ states.
Q9. The complement of a DFA with n states and alphabet Σ can be found by:
A) Adding ε-transitions
B) Reversing all transitions
C) Swapping final and non-final states
D) Doubling states
Answer: C
Explanation: Complementation of DFA is done by swapping accepting and non-accepting states.
Q10. The time complexity of minimizing a DFA with n states is approximately:
A) O(n)
B) O(n log n)
C) O(n²)
D) O(2ⁿ)
Answer: C
Explanation: Partition refinement algorithm runs in O(n²) in general.
Q11. Which of the following operations is not closed for regular languages?
A) Union
B) Intersection
C) Complement
D) None of these
Answer: D
Explanation: Regular languages are closed under union, intersection, and complement.
Q12. Two DFAs are equivalent if:
A) They have same number of states
B) They accept same set of strings
C) Their transition tables are identical
D) Both start from same initial state
Answer: B
Explanation: Equivalence depends on accepted language, not state count.
Q13. Which of the following is not a valid transition function for a DFA?
A) δ: Q × Σ → Q
B) δ: Q × Σ → 2^Q
C) δ: Q × Σ → Q, total function
D) δ(q, a) = q’ for some q’ ∈ Q
Answer: B
Explanation: That represents NFA. DFA has single next state, not a set.
Q14. Which of the following FA accepts all strings over {0,1} containing an even number of 0s?
A) 1 state
B) 2 states
C) 3 states
D) 4 states
Answer: B
Explanation: One state for even count, one for odd — toggle on reading 0.
Q15. If a DFA has 6 states, what is the maximum number of transitions possible over binary alphabet?
A) 6
B) 12
C) 36
D) 24
Answer: B
Explanation: Each state has 2 transitions ⇒ total = 6×2 = 12.
Q16. Which of the following is a non-regular language?
A) { aⁿb | n ≥ 0 }
B) { aⁿbⁿ | n ≥ 0 }
C) { a* }
D) { (ab)* }
Answer: B
Explanation: Requires counting both a’s and b’s — not regular.
Q17. The FA for language containing “aba” as a substring will have minimum number of states equal to:
A) 2
B) 3
C) 4
D) 5
Answer: C
Explanation: 4 states — each tracking prefix of “aba”.
Q18. DFA that accepts all binary strings divisible by 3 (treating binary as number) will require:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: B
Explanation: Remainders 0, 1, 2 → 3 states.
Q19. Which of these statements about NFA is true?
A) NFA cannot have multiple start states.
B) NFA transitions are deterministic.
C) NFA may have multiple transitions for same symbol.
D) NFA accepts more languages than DFA.
Answer: C
Explanation: NFAs allow multiple transitions for same input from a state.
Q20. The minimal DFA for (0+1)*01 has how many states?
A) 2
B) 3
C) 4
D) 5
Answer: C
Explanation: Need 4 states to track suffix “01” pattern.
Q21. A DFA that accepts all strings over {0,1} ending with “00” requires minimum:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: B
Explanation: DFA tracks suffixes “”, “0”, “00” → 3 states needed.
Q22. A DFA has 8 states. The maximum number of edges in its transition graph for binary alphabet is:
A) 8
B) 16
C) 32
D) 64
Answer: B
Explanation: Each state has 2 outgoing transitions ⇒ 8×2 = 16 edges.
Q23. The language accepted by the DFA which has only one state that is both initial and final and self-loops on 0 and 1 is:
A) ∅
B) {ε}
C) (0+1)*
D) {0,1}
Answer: C
Explanation: It accepts all strings as it loops on all symbols.
Q24. The complement of a regular language is always:
A) Regular
B) Context-free
C) Recursive only
D) Non-regular
Answer: A
Explanation: Regular languages are closed under complementation.
Q25. If a DFA has 4 states, how many distinct DFAs can be constructed on binary alphabet?
A) 2⁴
B) (2⁴)⁸
C) 2⁸
D) (2×4)⁸
Answer: B
Explanation: For each of 4 states and 2 inputs ⇒ 8 transitions; each can go to 4 targets → 4⁸ DFAs.
Q26. The number of possible DFAs over binary alphabet with exactly one state is:
A) 1
B) 2
C) 3
D) 4
Answer: D
Explanation: One state → 2 transitions (for 0 and 1) each can go to itself (1 way) × 2 possible accept states = 4.
Q27. Which statement about DFA minimization is false?
A) Unreachable states can be removed.
B) Equivalent states can be merged.
C) Resulting DFA may recognize different language.
D) Final DFA is unique up to isomorphism.
Answer: C
Explanation: Minimization preserves the language; only structure changes.
Q28. Which of the following conversions is not always possible?
A) NFA → DFA
B) DFA → Regular Expression
C) Regular Expression → DFA
D) DFA → PDA
Answer: D
Explanation: PDA accepts context-free languages; DFA ⊂ PDA but reverse is not equivalent.
Q29. In a DFA, how many accepting states are required to accept all strings over {0,1} with even number of 1’s?
A) 1
B) 2
C) 3
D) 4
Answer: B
Explanation: Two states track parity of 1’s (even/odd).
Q30. The intersection of two regular languages is:
A) Always regular
B) Always non-regular
C) Regular only if alphabets differ
D) None of these
Answer: A
Explanation: Regular languages are closed under intersection.
Q31. DFA for (a+b)*abb requires minimum:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: D
Explanation: Need 5 states to remember suffix of “abb”.
Q32. Which automaton can recognize palindromes over {0,1}?
A) DFA
B) NFA
C) PDA
D) Turing Machine
Answer: D
Explanation: Palindromes require two-way checking → only TM can handle.
Q33. For a language L, L′ (reverse) is regular if:
A) L is regular
B) L is context-free
C) L is recursive
D) None
Answer: A
Explanation: Regular languages are closed under reversal.
Q34. Which among the following cannot be expressed by a DFA?
A) Strings with even number of a’s
B) Strings ending with ab
C) Strings with equal number of a’s and b’s
D) Strings containing substring aa
Answer: C
Explanation: Equal counts need memory beyond finite states.
Q35. An NFA has states {q0,q1}, alphabet {a,b}, transitions: q0–a→q0,q1; q1–b→q1.
Which strings are accepted if q0 is start and q1 is final?
A) ab
B) a+b*
C) a* b+
D) a*b+
Answer: D
Explanation: Must read any number of a’s then at least one b.
Q36. The minimal DFA accepting all strings over {0,1} with exactly two 1’s has:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: D
Explanation: Tracks count of 1’s: 0,1,2,>2 ⇒ 4 states.
Q37. The complement of (0+1)*0 is:
A) (0+1)1 B) 0
C) 1*
D) 0+1
Answer: A
Explanation: Strings not ending with 0 ⇒ must end with 1.
Q38. The minimal DFA that accepts strings over {a,b} where every ‘a’ is immediately followed by ‘b’ has:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: B
Explanation: States: start, seen a (waiting for b), dead.
Q39. For DFA D, if L(D) = ∅, what property holds?
A) All states final
B) Start state non-final and no path to final
C) One final reachable
D) All transitions undefined
Answer: B
Explanation: Empty language means no accepting configuration reachable.
Q40. DFA equivalent to NFA with ε-moves can be built using:
A) Power set construction
B) Subset construction with ε-closure
C) Direct conversion
D) State elimination
Answer: B
Explanation: ε-closure used before processing each input symbol.
Q41. The DFA for { w | w has substring 101 } needs:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: B
Explanation: Tracks prefixes of “101”: ε,1,10,101.
Q42. Which among the following regular expressions generate same language?
A) (a+b)* = (b+a)*
B) (a+b)a = a(a+b)
C) (a+b)b = b(a+b)
D) None
Answer: A
Explanation: Order inside union doesn’t affect accepted set.
Q43. For an NFA with 3 states, what is the maximum number of ε-transitions possible?
A) 3
B) 6
C) 9
D) Infinite
Answer: B
Explanation: Each pair (i→j) can have ε-transition; 3×2=6 possible.
Q44. DFA that accepts all binary strings containing substring 00 but not 11 requires at least:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: C
Explanation: Must track both substring patterns simultaneously.
Q45. The DFA corresponding to (0+1)*1(0+1) accepts strings of length:
A) ≥1
B) ≥2
C) =2
D) ≥3
Answer: B
Explanation: Must have at least two symbols, ending second-last with 1.
Q46. A DFA can be minimized by:
A) Eliminating equivalent states
B) Removing self loops
C) Adding ε-transitions
D) Doubling final states
Answer: A
Explanation: Merge states indistinguishable by input strings.
Q47. The language { w | w has even number of 0s and odd number of 1s } needs minimum:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: 2×2 combinations of parity.
Q48. Two minimal DFAs for same language:
A) Must be identical
B) Must be isomorphic
C) May differ in language
D) None
Answer: B
Explanation: Unique up to renaming of states.
Q49. Regular language L over Σ = {a,b} where every string ends with “ab”. Minimal DFA has:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: Tracks suffixes “a”, “ab”, and mismatch → 4 total.
Q50. For DFA D1 and D2, L(D1) = Σ*, L(D2)=∅. Then L(D1)∩L(D2)=
A) Σ*
B) ∅
C) {ε}
D) {a,b}
Answer: B
Explanation: Intersection with empty set is empty.
Q51. A DFA that accepts strings over {a,b} containing “aa” as substring but not ending with “bb” needs minimum:
A) 4 states
B) 5 states
C) 6 states
D) 7 states
Answer: C
Explanation: 3 for “aa” + tracking of end pattern.
Q52. For DFA M, if L(M) = L(M)⁻ (complement), then L(M) is:
A) Σ*
B) ∅
C) Σ* or ∅
D) Both A and B
Answer: D
Explanation: Only possible when language is all or none.
Q53. Which is always true for DFA?
A) Has exactly one start state
B) May have multiple start states
C) Start state must be final
D) None
Answer: A
Explanation: DFA definition allows only one initial state.
Q54. DFA for (ab)* accepts:
A) Even-length strings alternating a,b
B) Odd-length strings
C) Strings ending with b
D) Only ε
Answer: A
Explanation: Repetition of “ab” pattern → even length.
Q55. If DFA accepts Σ*, what must be true?
A) Start state is final and all transitions defined
B) All states final
C) No final states
D) None
Answer: A
Explanation: Acceptance of all strings implies start reachable final path for any input.
Q56. DFA for binary strings with no two consecutive 1s has:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: B
Explanation: Tracks last read as 1 or not.
Q57. For every DFA M, there exists regular expression R such that:
A) L(M) = L(R)
B) L(M) ⊂ L(R)
C) L(M) ≠ L(R)
D) L(R) = ∅
Answer: A
Explanation: Regular expressions and DFA define same class.
Q58. Which of these languages cannot be represented by finite automaton?
A) {aⁿ | n even}
B) {aⁿbⁿ | n ≥ 0}
C) (a+b)*
D) (ab)*
Answer: B
Explanation: Needs counting → non-regular.
Q59. If DFA D has n states, then its complement DFA has:
A) n
B) n+1
C) 2n
D) n²
Answer: A
Explanation: Complementation swaps final/non-final, not count.
Q60. Which among the following operations may increase state count exponentially?
A) NFA→DFA conversion
B) DFA→NFA
C) DFA minimization
D) Complementation
Answer: A
Explanation: Subset construction causes 2ⁿ blow-up.
Q61. Which of the following automata can accept both finite and infinite languages?
A) DFA
B) NFA
C) Both DFA and NFA
D) None
Answer: C
Explanation: Both DFA and NFA can accept finite or infinite regular languages.
Q62. The DFA accepting all strings over {0,1} containing at least two 0’s and one 1 requires minimum:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: C
Explanation: Must track count of zeros and presence of at least one one.
Q63. The number of distinct strings of length 3 accepted by DFA with Σ = {0,1} and all states final is:
A) 4
B) 6
C) 8
D) 16
Answer: C
Explanation: (2 symbols)^3 = 8 total strings; all accepted.
Q64. If DFA D1 accepts Σ* and DFA D2 accepts ∅, then L(D1) ∪ L(D2) = ?
A) ∅
B) Σ*
C) {ε}
D) None
Answer: B
Explanation: Union with Σ* always gives Σ*.
Q65. Which of the following is true for a dead state in DFA?
A) Once entered, cannot be left.
B) Accepts all strings.
C) Always initial state.
D) Used only in NFA.
Answer: A
Explanation: Dead state has self-loops on all inputs; cannot reach final state.
Q66. Which of the following is not true about DFA minimization?
A) Merge equivalent states.
B) Delete unreachable states.
C) Add ε-transitions for simplification.
D) Use distinguishability method.
Answer: C
Explanation: ε-transitions not allowed in DFA.
Q67. The number of states in the DFA accepting binary strings not containing substring “11” is:
A) 2
B) 3
C) 4
D) 5
Answer: B
Explanation: Tracks “no 1 seen,” “1 seen,” and “11 seen (dead)”.
Q68. DFA accepting { w | w begins and ends with same symbol } over {0,1} needs:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: Track start symbol and ensure same end symbol.
Q69. The minimal DFA that accepts strings with at least one ‘0’ and one ‘1’ requires:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: Must track whether 0 and 1 have appeared.
Q70. DFA that accepts all binary strings that do not contain 000 as substring needs:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: B
Explanation: Tracks last up to 2 consecutive zeros.
Q71. If an automaton has a dead state, which of the following is true?
A) Language accepted is always empty.
B) Language may still be non-empty.
C) All states final.
D) All transitions lead to dead state.
Answer: B
Explanation: Dead state may exist but not reachable from start.
Q72. Which of the following automata can recognize the same class of languages as DFA?
A) NFA
B) PDA
C) TM
D) LBA
Answer: A
Explanation: NFA ≡ DFA in language recognition power.
Q73. The DFA accepting binary numbers divisible by 4 will have minimum:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: Divisible by 4 depends on last two bits ⇒ 4 possible remainders.
Q74. Which property holds for regular languages?
A) Closed under union
B) Closed under concatenation
C) Closed under reversal
D) All of these
Answer: D
Explanation: Regular languages are closed under all these operations.
Q75. DFA equivalent to regular expression (0+1)*11 has:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: B
Explanation: Tracks prefixes ε, “1”, “11”.
Q76. If DFA D1 and D2 accept L1 and L2, then DFA for L1 ∩ L2 is constructed using:
A) Product automaton
B) Union of transitions
C) Direct merge
D) Complementation
Answer: A
Explanation: Cartesian product of state sets used for intersection.
Q77. Which statement about regular languages is false?
A) Closed under reversal
B) Closed under intersection
C) Closed under complement
D) Closed under palindrome
Answer: D
Explanation: Palindromes are not regular.
Q78. The DFA for binary strings with odd number of 1’s and even number of 0’s requires:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: 2×2 parity combinations ⇒ 4 states.
Q79. If all states of a DFA are final, language accepted is:
A) ∅
B) Σ*
C) Finite
D) None
Answer: B
Explanation: Any string ends in some final state ⇒ Σ*.
Q80. DFA corresponding to regular expression 010 accepts:
A) Strings with exactly one 1
B) Strings ending with 0
C) Strings starting with 1
D) Only ε
Answer: A
Explanation: Any number of 0s, one 1, then 0s.
Q81. DFA for (a+b)a(a+b) accepts:
A) Strings with at least one a
B) Strings ending with a
C) Strings starting with a
D) None
Answer: A
Explanation: Must contain at least one ‘a’.
Q82. The minimal DFA for a language with exactly one substring “ab” needs:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: C
Explanation: Need states tracking before, during, after “ab”.
Q83. A DFA that accepts only ε requires minimum:
A) 1 state
B) 2 states
C) 3 states
D) 4 states
Answer: B
Explanation: One final start state and one trap state for any input.
Q84. A DFA with n states can accept at most how many distinct strings?
A) n
B) 2ⁿ
C) Infinite
D) Depends on transitions
Answer: C
Explanation: DFAs can accept infinite sets if loops exist.
Q85. Which operation preserves regularity?
A) Complement
B) Homomorphism
C) Intersection
D) All of these
Answer: D
Explanation: Regular languages are closed under all three.
Q86. DFA for even-length binary strings requires minimum:
A) 1 state
B) 2 states
C) 3 states
D) 4 states
Answer: B
Explanation: States alternate between even/odd length.
Q87. The set of all regular languages over Σ is:
A) Finite
B) Countably infinite
C) Uncountable
D) None
Answer: B
Explanation: Regular expressions form a countably infinite set.
Q88. In DFA, two states p and q are equivalent if:
A) They are final
B) They are start states
C) δ(p,x) and δ(q,x) accept same for all x
D) Both non-final
Answer: C
Explanation: Equivalence defined by identical language acceptance.
Q89. Regular language L = { w | number of 1’s even } → minimal DFA has:
A) 1 state
B) 2 states
C) 3 states
D) 4 states
Answer: B
Explanation: Two states for parity tracking.
Q90. DFA accepting { w | w ends with 101 } requires:
A) 3 states
B) 4 states
C) 5 states
D) 6 states
Answer: B
Explanation: Tracks prefixes of “101”.
Q91. Which among the following is regular?
A) {aⁿbⁿ | n≥0}
B) {aⁿbᵐ | n,m≥0}
C) {aⁿbⁿcⁿ | n≥0}
D) {aⁿbⁿ⁺¹ | n≥0}
Answer: B
Explanation: Independent counts of a’s and b’s → regular.
Q92. DFA with all final states reachable but no transitions to start state accepts:
A) All strings
B) Finite language
C) Empty language
D) Infinite but not all
Answer: D
Explanation: Depends on reachable transitions; can be infinite subset.
Q93. DFA recognizing even number of a’s and b’s needs minimum:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: Even/odd parity combination ⇒ 4 states.
Q94. A DFA is minimal if:
A) No unreachable states
B) No two equivalent states
C) Language unchanged
D) All of these
Answer: D
Explanation: All are properties of minimized DFA.
Q95. Regular language L satisfies L = L⁻ (complement). Then L must be:
A) Σ*
B) ∅
C) Both A and B possible
D) None
Answer: C
Explanation: Only ∅ and Σ* are self-complementary.
Q96. The language accepted by DFA D where all states are final is:
A) ∅
B) Σ*
C) Finite
D) Infinite
Answer: B
Explanation: Every string ends in final state ⇒ Σ*.
Q97. DFA accepting (a+b)*bb requires:
A) 2 states
B) 3 states
C) 4 states
D) 5 states
Answer: C
Explanation: Need 4 states to track suffix “bb”.
Q98. Regular language L = (ab+ba)* has strings of:
A) Even length only
B) Odd length only
C) Both
D) Only ε
Answer: A
Explanation: Each block has 2 characters ⇒ even length.
Q99. DFA equivalent to regular expression (0+1)0(0+1)0(0+1)* accepts strings having:
A) At least one 0
B) At least two 0s
C) Even number of 0s
D) Ends with 0
Answer: B
Explanation: Two 0s at arbitrary positions.
Q100. If DFA accepts no string, then:
A) Start = Final
B) Start non-final and no path to final
C) All states final
D) All transitions undefined
Answer: B
Explanation: No reachable final ⇒ language empty.
About the Author
