GATE Solved Paper 2020 - GATE 2020

52. Consider the following language.
number of a’s in x is divisible by 2 but not divisible by 3
The minimum number of states in a DFA that accepts L is ____.

  • Option : C
  • Explanation :
    L = w ϵ (a, b)* |na(w) = multiple of 2 but not 3.
    L1 = {na mod 2 = 0} ⇒ need 2 states
    L2 = {na mod 3 ≠ 0} ⇒ need 3 states
    |L1 × L2| = (2 × 3) = 6 states.
    Minimal DFA design ⇒
    Gate2020 cs
    ∴ No. of states in min. DFA = 6 states.
Cancel reply
Cancel reply