Consider the language \(L\) given by \(L=\{ 2^{nk} \mid k >0, \text{ and n is…

Answer: n + 1

Construction (upper bound): Build a DFA with n+1 states as follows.

• One start state that is non-accepting to ensure the empty string is not accepted.

• n states that represent remainders 0,1,…,n-1 modulo n after at least one symbol has been read.

• On symbol '2' transition from the start state to the remainder-1 state, and from remainder i go to remainder (i+1) mod n.

• Make the remainder-0 state accepting; this accepts exactly strings whose length is a positive multiple of n.

Minimality (lower bound):

• Consider the n+1 strings of lengths 0,1,2,…,n-1 (i.e., strings with 0,1,…,n-1 copies of the symbol).

• For two distinct lengths i and j with 0 ≤ i < j ≤ n-1, appending a block of length n−i makes the total length a positive multiple of n for the string of length i but not for the string of length j. Thus these two strings are distinguishable by future continuations.

• Hence there are at least n+1 pairwise distinguishable equivalence classes, so any DFA needs at least n+1 states (Myhill–Nerode).

Combining the construction and the minimality argument gives that the minimum number of states required is n+1.