# Show that if S is an arithmetic progression, then A can be recognized by a DFA [duplicate]

A set S of nonnegative integers is called an arithmetic progresion if there exist some integers n and p such that

S = {n + ip : i ≥ 0}

Let A ⊆ {a}∗ and consider S = {| x |: x ∈ A}.

(1) Show that if S is an arithmetic progression, then A can be recognized by a

DFA

(2) Show that if A can be recognized by a DFA, then S is the union of a ﬁnite number of arithmetic

Consider, for example, the series $\langle\,3, 7, 11, 15, 19, \dotsc\,\rangle$. That's an arithmetic progression $n+ip$ with $n=3, p=4$. You're asked for the language over $\{a\}$ consisting of all strings with lengths in that series, namely $$L = \{aaa, aaaaaaa, aaaaaaaaaaa, aaaaaaaaaaaaaaa, \dotsc\}$$ You're asked for a DFA that will accept all and only those strings.
Hint: It'll consist of a chain of states that lead to a final state after reading three $a$'s and then continue with a loop that will lead you back to that final state after seeing four more $a$'s.