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

309 Views Asked by At

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

There are 1 best solutions below

5
On

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