Question

Definition of a language L with alphabet {a} is given as follows:

$L=\{a^{nk}\mid k>0,andnisapositiveintegerconstant\}.$

What is the minimum number of states needed in a dfa to recognize L?

Answer 1

Let n = 3(say)

then L = $\{a^{3k}\mid k>0\}=\{a^{3k}\mid k\ge 1\}$

The dfa for this will be

which has 4 states.

Similarly for $L=\{a^{nk}\mid k>0\}$, we will need n + 1 states.