1
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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*}

$\endgroup$
  • 1
    $\begingroup$ $h: A^* \to \mathcal{P}(M) \times M\ $ I am not sure if h is epimorphism ( suriective morphism). $\endgroup$ – user180834 Apr 14 '15 at 14:37
  • 1
    $\begingroup$ @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. $\endgroup$ – J.-E. Pin Apr 14 '15 at 14:54
  • $\begingroup$ 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? $\endgroup$ – user180834 Apr 14 '15 at 15:14
  • $\begingroup$ 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. $\endgroup$ – user180834 Apr 14 '15 at 19:59
  • $\begingroup$ $\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')$. $\endgroup$ – J.-E. Pin Apr 14 '15 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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