GATE 2020 CS – Question 61
Consider the following language.
$L=\{x\in\{a,b\}^*\mid$ 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 ______.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 6 to 6
Explanation
The DFA tracks the count of a's modulo 6 (lcm of 2 and 3). Accepting residues are 2 and 4, and all 6 residue classes are distinguishable. Minimum states = 6.