# Does the following operation makes the language regular? [duplicate]

I came across a question stated as $$L = \{wxwy \mid w \in \{0,1\}^* , x,y \in\{ 0,1\}^* \}$$ is regular and I have no problem understanding it.

However I thought what could happen if the language is modified to $$L = \{wxw \mid w \in \{0,1\}^+ , x \in\{ 0,1\}^* \}$$.

In my opinion the above language is regular and it represent not what is seen by naked eyes, by that I mean the above language could be written as $$L=(0+1)^*$$. Please correct me if I am wrong.

• Hint: is the string $01$ in $L$? If you think yes, what is a possible interpretation for $w$?
– orlp
Dec 5 '18 at 4:14
• @orlp no the string 01 is not in L, so this means that "x" would not be able to cover all the "w" meaning it not regular ? iam i correct? Dec 5 '18 at 4:30
• @HendrikJan In that question, $x\in\{0,1\}^+$, while in this question $x\in\{0,1\}^*$. Dec 6 '18 at 7:12
• @xskxzr True, but the pumping argument to the earlier question applies here too. Dec 6 '18 at 12:01

## 1 Answer

Interesting question. As Orlp pointed out, $$L$$ does not contain 01. So it cannot be $$(0+1)^*$$.

In fact $$L$$ is not regular. Consider $$M=L\cap L(0^+110^+1)$$.

Claim. $$M=\{0^i110^i1\mid i\gt0\}$$.
Proof. Since $$(0^i1)1(0^i1)\in M$$ for $$i>0$$, we have the "$$\supseteq$$". Now suppose $$wxw=00^i110^j1$$, $$w\in\{0,1\}^+$$, $$x\in\{ 0,1\}^*$$, $$i,j\ge0$$. then $$w$$ must starts with 0 and ends with 1. Since there only three 1's in $$wxw$$, $$w=00^i1$$ and $$x=1$$. So $$wxw=00^i1100^i1$$, $$i\ge0$$. We have the "$$\subseteq$$".

There is a counting requirement for words in $$M$$. So, intuitively, $$M$$ cannot be regular. I will let you prove it rigorously using, for example, the pumping lemma for regular language.

Since $$M$$ is not regular and $$0^+110^+1$$ is regular, $$L$$ cannot be regular.