Consider the following language. L = \x ∈ \a, b\^* 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 _______.

GATE CSE 2020 Q61: Minimum DFA states: number of a's divisible by 2 but not by 3

Consider the following language.

$L = \{x \in \{a, b\}^* \mid \text{number of } a\text{'s in } x \text{ is divisible by 2 but not divisible by 3}\}$

The minimum number of states in a DFA that accepts $L$ is _______.

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 6 (official GATE 2020 final answer key)

Concept used: Track the count of a's modulo $\text{lcm}(2, 3) = 6$ ; then check whether any residues are equivalent.

First step: Accepting residues mod 6 are 2 and 4; check that every pair of the six residue states is distinguishable by some suffix of a's.

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2020 CS question paper and final answer key, organised by IIT Delhi. Question paper · Answer key