Minimum number of states needed?

Question

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

L = { a^nk | k > 0 ; and n is a positive integer constant }

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

---

In my opinion it should be k+1 but I am not sure.

Answer 1

The language L can be recognized by a DFA with n+1 states.

Observe that the length of any string in L is congruent to 0 mod n.

Label n of the states with integers 0, 1, 2, ... n-1, representing each possible remainder. An additional state, S, is the start state. S has a single transition, to state 1. If the machine is currently in state i, on input it moves to state (i+1) mod n. State 0 is the only accepting state. (If the empty string were part of L, we could eliminate S and make state 0 the start state).

Suppose there were a DFA with fewer than n+1 states that still recognized L. Consider the sequence of states S₀, S₁, ... S_n encountered while processing the string aⁿ. S_n must be an accepting state, since aⁿ is in L. But since there are fewer than n+1 distinct states in this DFA, by the pigeonhole principle there must have been some state that was visited at least twice. Removing that loop gives another path (and another accepted string), with length < n, from S₀ to S_n. But L contains no strings shorter than n, contradicting our assumption. Therefore no DFA with fewer than n+1 states recognizes L.