[Solved]: Proving Regularity of Languages that are 1/k of an already known regular language

Problem Detail: 

There is this question in Kozen, that states if a language is regular then the first half would also be regular. Also I found a material on the internet that extends the thinking saying a language that is two-thirds of already known regular language is regular. I'm tempted to think that it should also hold true for any general $k>0$ that $m/k$th ($1 \leqslant m \leqslant k-1$) portion of a regular language would also be regular. I need a mathematical proof ( or a constructive proof having mathematical verifications done on it ) for the above statement.
EDIT: For the "first half Language" which is much better formalised by David in the comments, I tried a similar argument as the answer in the link given by Hendrik. The product automaton notion was intuitively clear. But I was stuck with the transition listings for the 2nd state in the pair of states so formed by constructing the product automaton. I was flummoxed as to how I could be able to get the exact state for the corresponding word 'w' which would be the "first half" of a word accepted by the original regular language.

Asked By : Ramit

Answered By : J.-E. Pin

Let $L$ be a regular language and let $(p, q) \in \mathbb{N}^2$. Then the following language is regular: $$ L_{p,q} = \{ u \in A^* \mid \text{there exist $x$ and $y$ in $A^*$ such that $|x| = p|u|$, $|y| = q|u|$ and $xuy \in L$} \} $$ Furthermore, for any subset $S$ of $\mathbb{N}^2$, the language $$ L_S = \bigcup_{(p,q,r) \in S} L_{p,q} $$ is also regular. I would like to insist that it works for any any subset $S$, including non recursively enumerable subsets of $\mathbb{N}^2$, which might look a little bit suspicious at first glance...

You can try to prove these results by using automata, but it is much easier to use the fact that a language is regular iff it is recognized by a finite monoid.

Let $L$ be a regular language of $A^*$. It is recognized by a finite monoid $M$, that is, there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Now $\mathcal{P}(M)$, the powerset of $M$, is also a finite monoid under the multiplication defined, for $X, Y \in \mathcal{P}(M)$, by $XY = \{ xy \mid x \in X, y \in Y\}$.

Let now $h: A^* \to \mathcal{P}(M) \times M$ be the monoid morphism defined, for each letter $a \in A$, by $h(a) = (f(A), f(a))$. Then for each word $u$, $h(u) = (f(A^{|u|}), f(u))$. I claim that $L_{p,q} = h^{-1}(Q)$ where $$ Q = \bigl\{(R,m) \in \mathcal{P}(M) \times M \mid R^pmR^q \cap P \not= \emptyset \bigr\}. $$ and similarly $L_S = h^{-1}(T)$ where $$ T = \Bigl\{(R,m) \in \mathcal{P}(M) \times M \mid \Bigl(\bigcup_{(p,q) \in S}R^pmR^q\Bigr) \cap P \not= \emptyset \Bigr\}. $$ Thus $L_{p,q}$ and $L_S$ are recognized by the finite monoid $\mathcal{P}(M) \times M$ and hence are regular.

Proof of the claim. \begin{align*} h^{-1}(Q) &= \{u \in A^* \mid (f(A^{|u|}), f(u)) \in Q \} \\ &= \{u \in A^* \mid f(A^{p|u|}f(u)f(A^{q|u|}) \cap P \not= \emptyset \} \\ &= \{u \in A^* \mid f(A^{p|u|}uA^{q|u|}) \cap P \not= \emptyset \} \\ &= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap f^{-1}(P) \not= \emptyset \} \\ &= \{u \in A^* \mid A^{p|u|}uA^{q|u|} \cap L \not= \emptyset \} \\ &= L_{p,q} \end{align*}

Best Answer from StackOverflow

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