# show that language $L'$ is regular (given $L$ regular)

Let $L$ be a regular language. Show that $L'=\{x \mid\exists_{y,z} xyz\in L \text{ and }|x|=|y|=|z|\}$ is also regular.

Firstly I show my idea. When you accept it I will try to formalize it. Every automat can have exactly one accept state. So let automat for language $L$ has exactly one accept state.

And now we start in two place - in $q_0$ and $a_{accept}$. From $a_{accept}$ we guess symbol. For one symbol we do two steps. From $q_0$ we go according to symbol - one step. State accepting is when two "starts" meet in one state.

What about idea ?

## 1 Answer

You can try to answer this question (and other questions you posted) by using automata, but you can also use another way.

Definition. A language $L$ of $A^*$ is recognized by a monoid $M$ if there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$.

Fact. A language is regular if and only if it is recognized by some finite monoid.

Let $L$ be a regular language. Then there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$. Observe that $\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' = h^{-1}(Q)$ where $$Q = \bigl\{(R,m) \in \mathcal{P}(M) \times M \mid RmR \cap P \not= \emptyset \bigr\}.$$ Thus $L'$ is recognized by the finite monoid $\mathcal{P}(M) \times M$ and hence is regular. In fact $L'$ is recognized by the smaller monoid $C \times M$ where $C$ is the submonoid of $\mathcal{P}(M)$ generated by $f(A)$.

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^{|u|}f(u)f(A^{|u|}) \cap P \not= \emptyset \} \\ &= \{u \in A^* \mid f(A^{|u|}uA^{|u|}) \cap P \not= \emptyset \} \\ &= \{u \in A^* \mid A^{|u|}uA^{|u|} \cap f^{-1}(P) \not= \emptyset \} \\ &= \{u \in A^* \mid A^{|u|}uA^{|u|} \cap L \not= \emptyset \} \\ &= L' \end{align*}

• $h: A^* \to \mathcal{P}(M) \times M\$ I am not sure if h is epimorphism ( suriective morphism). – user180834 Apr 14 '15 at 14:37
• @user180834 You are perfectly right. In fact the condition "surjective" is not mandatory, since you can always replace $M$ by $f(M)$ in the definition. – J.-E. Pin Apr 14 '15 at 14:54
• Thanks! "You can try to answer this question (and other questions you posted) by using automata, but you can also use another way. " Could you refer me, please? – user180834 Apr 14 '15 at 15:14
• Ok, last question: You define homomorhism: $h: A^* \to \mathcal{P}(M) \times M\$ But I don't understand why $\mathcal{P}(M) \times M\$ is monoid, and what is operation. – user180834 Apr 14 '15 at 19:59
• $\mathcal{P}(M)$ is a monoid, as indicated in my answer. Now, the product of two monoids $M$ and $N$ is the cartesian product $M \times N$, with the multiplication given by $(m,n)(m',n') = (mm', nn')$. – J.-E. Pin Apr 14 '15 at 20:18