# How to find the minimum number of states required by a DFA

Given a language $L = \left\{ a^{nk+1} | n > 0 \right\}$ and $k$ is an integer constant.

How to show that a DFA for this language must have $k+2$ states or more states using minimum state lemma.

By minimum state lemma I mean the number of minimum state a DFA has is the number of pairewise distinguishable states. I have constructed a set of pairewise distinguishable string ${a, aa, aaa, ... a^{k+2}}$ with respect to L and found that I can not add anymore strings to it. But I don't know how to prove this string has the maximum number of pairewise distinguishable strings.

• What do you think? What have you tried, and where have you failed? Also, can you state the "minimum state lemma"? This is not a standard term, though I'm sure it refers to some form of the Myhill–Nerode theorem. Feb 26 '17 at 21:58
• @junhong: why do you care how much bigger the set could be? You only need to prove a minimum DFA size.
– rici
Feb 26 '17 at 22:51
• In the other direction, it suffices to construct a DFA with the minimum number of states. this gives you an upper bound on the maximum number of pairwise distinguishable strings. Feb 26 '17 at 23:43

Note, however, that the question only asks you to show that every DFA for the language must contain at least $k+2$ states. For this there is no need to show that your collection is maximal. If you find $k+2$ pairwise inequivalent strings, then it follows that every DFA for the language must contain at least $k+2$ states. If the collection is not maximal, all it means is that your bound isn't tight.
• Given an arbitrary string, you have to show that it's equivalent to (in your case) one of $a,a^2,\ldots,a^{k+2}$. Feb 27 '17 at 0:34