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

574 Views Asked by At

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.

2

There are 2 best solutions below

1
On BEST ANSWER

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

6
On

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.