The Pumping Lemma

3. Let L be a regular language with m states. Clearly, if its DFA M accepts some string of length less than m, then L is non-empty

Prove that if L is non-empty, then M accepts a string w with |w| < m. (Hint: If L is non-empty, let w L be as short as any word in L. If |w| m, use the pumping lemma to derive a contradiction that w is among the shortest words accepted by M.