[Solved]: Prove Language Is Union of Fninitely Many Arithmetic Progressions

Problem Detail: 

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

Asked By : levi

Answered By : sdcvvc

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42475

3.2K people like this

 Download Related Notes/Documents