2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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