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.
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^qBigr) 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
