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.

  • 1
    $\begingroup$ Hint: is the string $01$ in $L$? If you think yes, what is a possible interpretation for $w$? $\endgroup$
    – orlp
    Dec 5 '18 at 4:14
  • $\begingroup$ @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? $\endgroup$
    – rballiwal
    Dec 5 '18 at 4:30
  • $\begingroup$ @HendrikJan In that question, $x\in\{0,1\}^+$, while in this question $x\in\{0,1\}^*$. $\endgroup$
    – xskxzr
    Dec 6 '18 at 7:12
  • $\begingroup$ @xskxzr True, but the pumping argument to the earlier question applies here too. $\endgroup$ Dec 6 '18 at 12:01

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.


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