The GATE Grind

GATE 2020 CS – Question 61

Theory of Computation · Regular Expressions and Finite Automata · 2 marks · Numerical answer

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

Let $n_a$ be the number of $a$'s. The language needs $n_a\equiv0\pmod2$ **and** $n_a\not\equiv0\pmod3$. Whether $n_a$ is divisible by both 2 and 3 depends on $n_a\bmod6$, so the DFA must track $n_a\bmod6$ (6 states, the `b`'s do not change the state).

Accepting residues: even and not a multiple of 3: $n_a\bmod6\in\{2,4\}$. (Residue 0 is divisible by 3; residues 1, 3, 5 are odd.)

All 6 states are pairwise distinguishable (appending `a`'s from a state reaches an accepting residue after a different number of steps), so the minimum DFA has **6** states.

More Regular Expressions and Finite Automata questions

All Regular Expressions and Finite Automata questions →