-1
$\begingroup$

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

$\endgroup$
  • 4
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 12 '15 at 19:11
  • 3
    $\begingroup$ $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. $\endgroup$ – David Richerby May 12 '15 at 19:29
  • $\begingroup$ @YuvalFilmus yes, of course. I updated the sentence. I just meant that everything until the last line makes sense to me. Thanks for correction. $\endgroup$ – levi May 13 '15 at 7:30
  • 1
    $\begingroup$ 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! $\endgroup$ – Raphael May 13 '15 at 8:17
  • $\begingroup$ @DavidRicherby, Yes agree with that. Furthermore, that's why I asked this question. There was no definition for that. $\endgroup$ – levi May 13 '15 at 8:19
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Thanks for the answer. Also informal learning just happened from your answer text and I translated image to the LaTex. $\endgroup$ – levi May 14 '15 at 21:18

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