# Prove Language Is Union of Fninitely Many Arithmetic Progressions [closed]

So, you see in the image the question and its answer (proof below the black line).

I get the entire proof until the last formula. It basically says that if length of a string is larger than number of states then one or more states need to be re-visited (at least one more times).
Formula for the L makes also perfect sense. It is union of strings like a^m when m < j (explained above in the image) and a^m+(i-j)l (also explained in the picture).

I do not get the P(h[L])= formula. What is h[L]? And what is P(h[L])?

And one more question: How does this proof correspond to the question that {n:a^n ∈ L} is a union of finitely many arithmetic progressions?

Question: An arithmetic progression $\{p+ qn : n = 0,1,2,...\}$ for some $p,q ∈ N.$ Show that if $L \subseteq \{a\}^{\ast}$ is regular, then $\{n : a^n \in L \}$ is a union of finitely many arithmetic progressions.

Proof: Let $M = (K, \{a\}, δ, s, F)$ be a $DFA$ accepting L, and consider the set $K' \subseteq K$ of states which are reachable from the start state $s$. Since there is only one character in the alphabet, there is exactly one transition out of every state; thus, if we imagine reading the string $a^n$, we must pass through a series of states $q_0,q_1,...,q_n,$ and if $n > |K|$, then there exist $0\leq j < i \leq n$ such that $q_i = q_j$. Effectively, then the reachable portion of $M$ consists of a chain of states, each with a transition to the next on the character $a$, followed by a loop of states. Thus, the strings accepted by the $DFA$ are, for any $m < j$ such that $q_m$ is finalm $a^m$, and for any $m \geq j$ such that $q_m$ is final $a^{m+(j-i)l}$ for all $l \geq 0.$
Thus $L = \bigcup \{\{a^m\}:m < j, q_m \in F\} \cup \bigcup \{\{a^{m+(j-i)l}:l \geq 0\}: m \geq j, q_m \in F\}$, so
$$P(L) = \bigcup \{\{m+0l:l \geq 0\}: m < j, q_m \in F\} \cup \bigcup \{\{m+(j-i)l: l \geq 0\}: m \geq j, q_m \in F\}$$

• I'm not sure you can say that you get the entire proof if you don't understand what some of the symbols mean, and you're not sure what the proof actually proves. May 12, 2015 at 19:11
• $h[L]$ and $P(h[L])$ are not standard notation that I'm familiar with. So they should have been defined somewhere in the text before the part you've included. May 12, 2015 at 19:29
• @YuvalFilmus yes, of course. I updated the sentence. I just meant that everything until the last line makes sense to me. Thanks for correction.
– levi
May 13, 2015 at 7:30
• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! May 13, 2015 at 8:17
• @DavidRicherby, Yes agree with that. Furthermore, that's why I asked this question. There was no definition for that.
– levi
May 13, 2015 at 8:19

There is definitely a typo in the text; the sum in the final equation looks like $$\bigcup \{\{m + 0l\}\} \cup \bigcup \{\{a^{m+(j-i)l}\}\}$$, while $$\bigcup \{\{m + 0l\}\} \cup \bigcup \{\{m+(j-i)l\}\}$$ seems more logical.

I suggest to define $$P$$ in the task as:

Show if $$L \subseteq \{a\}^{\ast}$$ is regular, then $$P(L) = \{n:a^n \in L\}$$ is a union of finitely many arithmetic progressions.

and make the final sentence the following:

Thus $$L = \bigcup \{\{a^m\}:m < j, q_m \in F\} \cup \bigcup \{\{a^{m+(j-i)l}:l \geq 0\}: m \geq j, q_m \in F\}$$, so

$$P(L) = \bigcup \{\{m+0l:l \geq 0\}: m < j, q_m \in F\} \cup \bigcup \{\{m+(j-i)l: l \geq 0\}: m \geq j, q_m \in F\}$$

• Thanks for the answer. Also informal learning just happened from your answer text and I translated image to the LaTex.
– levi
May 14, 2015 at 21:18