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\}$$