# Is the language $\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \}$ regular?

This is a question from Iran's national grad school entrance exam. In the answers key, the answer was that the following language is regular but I doubt it is true, I proved using pumping lemma that it isn't regular, but I wanna make sure that my proof is correct. Please check my proof, and tell me your idea. Is this language regular?? $$\{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \}$$

I argued that using the string $s = 1^P 0^P 1 0^P 1^P$ that is a member of the language, can not be pumped. Because using the third condition of the pumping lemma $|xy|\leqslant P$ so the $y$ part only consists of $1$s and if it can be pumped $xyyz$ must be a member the language , but the $xyyz$ has more $1$s in the first part than the last part of the string so it isn't a member of the language, thus it can't be pumped, thus the language isn't regular.

Let $A = \{0, 1\}$ be the alphabet and let $$L = \{yxzx^Ry^R \mid x,y,z \text{ belongs to } \{0,1\}^+ \}$$ I claim that $L$ is regular and equal to $K$, where $$K = 00A^+00 \cup 01A^+10 \cup 10A^+01 \cup 11A^+11$$ Proof. If $u \in L$, then $u = yxzx^Ry^R$ for some words $x,y,z \in A^+$. Let $v = yx$. Observing that $v^R = x^Ry^R$, we get $u \in vA^+v^R$. Moreover, since $|v| \geqslant 2$, $vA^+v^R \subset K$. Thus $L \subseteq K$.

To prove the opposite inclusion, consider a word $u \in K$. By construction, $v = abzba$ for some letters $a, b \in A$ and some word $z \in A^+$. It follows that $K \subseteq L$, whence $K = L$.

• thank you , can you make me understand my problem with my claim. – FazeL Jul 15 '15 at 13:54

The language is regular. It’s the union of the following four languages, each of which is clearly regular:

\begin{align*} L_1=\left\{00z00:z\in\{0,1\}^+\right\}\\ L_2=\left\{11z11:z\in\{0,1\}^+\right\}\\ L_3=\left\{01z10:z\in\{0,1\}^+\right\}\\ L_4=\left\{10z01:z\in\{0,1\}^+\right\}\\ \end{align*}

The problem with your pumping lemma argument is that the pumped word can be decomposed as $11z11$ for some $z\in\{0,1\}^+$: it doesn’t have to be broken up in the way that you tried to use.

• thank you, but I don't understand the way you disproved my claim, can you make it more clear?? – FazeL Jul 15 '15 at 13:51
• @FazeL: Do you understand why those four languages are regular? – Brian M. Scott Jul 15 '15 at 13:55
• yes I do @Brian – FazeL Jul 15 '15 at 13:56
• @FazeL: Okay; do you see that their union really is the language in the question? Or is that where you’re having a problem? – Brian M. Scott Jul 15 '15 at 14:00
• Fu** I've just got it. thank you @Brian – FazeL Jul 15 '15 at 14:03