Back to the 2024 paper

Module 1: Introduction & Regular Languages

20242m

A DFA can have:

(i) Multiple start states
(ii) Multiple accepting states
(iii) Transitions on ε\varepsilon
(iv) None of the above

Worked SolutionAI Assisted

Answer

Correct Option: (ii) Multiple accepting states

Explanation

DFA definition: M=(Q,Σ,δ,q0,F)M = (Q,\Sigma,\delta,q_0,F)

  • q0q_0: Exactly one start state → (i) multiple start states false. (NFA can have multiple, DFA has one).
  • F⊆QF \subseteq Q: Set of final/accepting states. Can be 0, 1, or multiple → (ii) true. Example even number of 0's DFA has 1 accept, but language (a+b)∗ab(a+b)^*ab needs 1, language “ends with 00 or 11” needs 2.
  • Transitions: δ:Q×Σ→Q\delta: Q \times \Sigma \rightarrow Q is total deterministic, no ϵ\epsilon-moves. ϵ\epsilon-transitions allowed only in ϵ\epsilon-NFA → (iii) false.

Final Answer

DFA can have multiple accepting states → Option (ii).

Similar questions

Official AppAndroid App

PYQDeck for Android

Solve BEU previous-year exam papers anywhere, anytime. Fast search, offline paper viewing, and step-by-step solutions designed specifically for your phone.