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.
 A: 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.
A: 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$.
