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


(2) Show that if A can be recognized by a DFA, then S is the union of a finite 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.

With this in mind, you might be able to figure out question (2). If you've seen the Pumping Lemma for regular languages, its proof will give you a hint.


Not the answer you're looking for? Browse other questions tagged or ask your own question.