Proving that the next language is regular

Question

I was asked to prove that the next language is a regular language but I can't seem to understand why it is. The language is above {0,1} and defined as :{ $xy^Rzyx^R$ : $ |x| , |y| , |z| >=1$ }

Thank you for the help!

Answer 1

Let $L$ be your language. First observe that $L$ contains the languages:

1. $L_1 = 00\{0,1\}^+00$ (corresponding to the case $x = y = 0$),
2. $L_2 = 01\{0,1\}^+10$ (case $x = 0$, $y = 1$),
3. $L_3 = 10\{0,1\}^+01$ (case $x = 1$, $y = 0$),
4. $L_4 = 11\{0,1\}^+11$ (case $x = 1$, $y = 1$).

I claim that $L = L_1 \cup L_2 \cup L_3 \cup L_4$. It just remains to prove the inclusion $L \subseteq L_1 \cup L_2 \cup L_3 \cup L_4$. Let $w \in L$. Then $w = xy^Rzyx^R$ for some $x,y,z \in \{0,1\}^+$. Now the prefix of length $2$ of $w$ is equal to the reverse of its suffix of length $2$. It follows that $w \in L_1 \cup L_2 \cup L_3 \cup L_4$, which proves the claim.