5
$\begingroup$

I'm trying to prove that $L = \{ww^R : w \in \{a,b\}^*\}$ ($w^R$ is the reverse of $w$) is not regular using the pumping lemma.

Let $p$ be the pumping length and $s = a^pbba^p$.

$x = \epsilon$, $y = a^p$, $z = bba^p \implies s = \epsilon a^p bba^p = a^pbba^p$

1) Was $s$ properly divided?

Let's see:

$|xy| \leq p$

$|y| > 0$ (I'm not sure about this since $|y|$ depends on $p$?)

If we take $i = 2$, $xyyz = \epsilon a^p a^p bba^p \notin L$, so $L$ is not regular.

2) What about $i = 0$? $xz = \epsilon bba^p \notin L$, so $L$ is not regular.

$\endgroup$
  • 2
    $\begingroup$ I'm not sure to fully understand what your first part is about...When proving that a language is not regular, you assume that it satisfies the pumping lemma, and then show a contradiction. But when you assume it satisfies the pumping lemma, you don't choose how it is split. You assume that there exists $N$, such that $\forall w \in L, |w| > N \implies \exists x,y,z$ such that $w=xyz,|xy| \leq N,|y| \leq 1$ and $\forall i \geq 0, xy^iz \in L$ $\endgroup$ – yago May 8 '14 at 20:37
6
$\begingroup$

The hard part about these kinds of arguments is getting the quantifiers right. The pumping lemma says:

If $L$ is regular, then there exists a $p \ge 1$, such that for all $w \in L$ with $|w| \ge p$, there exists a "splitting" $w = xyz$, such that for all $i \ge 0$, $xy^iz \in L$.

You can think of this as an adversarial game. You pick a $p$, your opponent picks a $w$, you pick the $xyz$, they pick the $i$. If you can show it's in $L$, you win. So, the pumping lemma can be thought of as: if $L$ is regular, you can always win this game.

Therefore, if you lose, the language is not regular. So let's switch the roles; you are now the aggressor. Your opponent picks a $p$, you pick a $w$, they pick a splitting, you pick an $i$, and if you can always win, then $L$ is not regular. This can be phrased more mathematically: (note that the quantifiers are now switched!)

Let $L$ be a language. If for all $p \ge 1$, there exists a $w \in L$ with $|w| \ge p$, such that for all "splittings" $w = xyz$, there exists an $i \ge 0$ such that $xy^iz \notin L$, then $L$ is not regular.

So when proving languages are not regular, you don't get to pick how it splits!


What we have to do is pick our $w$ very carefully. I'll phrase this as a game first, then as a proof.

Let your opponent pick $p$. We'll choose $w = a^pbba^p$. No matter how our opponent splits the string, the conditions of the game/lemma require that $|xy| \le p$. So $xy$ consists only of $a$s, and cannot contain the $b$s. We choose $i = 0$, which will cause the $a$s to be asymmetric, and $xz \notin L$.

Assume $L$ is regular, for the sake of contradiction. Then $L$ satisfies the pumping lemma, so let $p$ be the pumping length. Consider $w = a^pbba^p$, where $a, b \in \Sigma$, $a \ne b$. Since $|w| = 2p + 2 \ge p$, there is some splitting $w = xyz$ satisfying the lemma. Since we know $|xy| \le p$, it must be that $x = a^k$ and $y = a^\ell$, with $k + \ell \le p$ and $\ell > 0$. This means that $z = a^{p-k-\ell} bb a^p$. Let $i = 0$, which gives $xz = a^{p - \ell} bb a^p$, which is not in $L$. By contradiction, $L$ is irregular.


By "splitting", I mean strings $x$, $y$, $z$ in $\Sigma^\ast$ such that $w = xyz$, $|xy| \le p$, and $|y| > 0$.

$\endgroup$
  • $\begingroup$ I'm a bit confused. First of all, you chose $w = a^pba^p$, which is not in $L$. Then you say "Since we know $|xy| \ge p$". I think it should have been $|xy| \leq p$. Aside from that, you know that there is some splitting satisfying the lemma, and you say "it must be that $x = a^k$ and $y = a^\ell$" -> aren't you splitting the string which is something (I thought) you said we don't? $\endgroup$ – David Robert Jones May 9 '14 at 0:33
  • $\begingroup$ Oh, sorry, I should have two $b$s there. (I rewrote this from an argument about palindromes). What I meant about the splitting is that *we* don't get to choose which splitting it is. But because of the size requirements of $xy$, we know what form it has to take. So whatever the "correct" splitting is, $x=a^k$. I'll edit the fixes in. $\endgroup$ – Henry Swanson May 9 '14 at 0:38
  • $\begingroup$ Does the fact $|xy| \leq p$ necessarily means that $y$ must contain only a's? In the end I think that what you are doing is splitting the string. $\endgroup$ – David Robert Jones May 9 '14 at 0:40
  • $\begingroup$ The difference is that, in your question, you're saying "y is $a^p$", where $p$ is the pumping length. But what I'm trying to get at is that y could be $a$, $aa$, $aaa$, ... But importantly, we can show that it must be $a^k$ for some $k$. $\endgroup$ – Henry Swanson May 9 '14 at 0:44
  • $\begingroup$ Here's my reasoning: I assume that $L$ is regular. Let $p$ be the pumping length. Since $L$ is regular, any string in $L$ of length $\geq p$ may be dividied into three pieces (I'm taking Sipser here), s = xyz, satysfing: 1) for each $i \geq 0$, $xy^iz \in L$, 2) $|y| > 0$, 3) $|xy| \leq p$, I took $x = \epsilon$, $y = a^p$, $z = bba^p$. $s = \epsilon a^p bba^p = a^pbba^p$ is in $L$, so $s = xyz$ should satisfy those three properties. What's wrong with my reasoning? $\endgroup$ – David Robert Jones May 9 '14 at 1:05
0
$\begingroup$

Note that this is true only if $|\Sigma|>1$, since for $|\Sigma|=1$, the language would just be $\Sigma^*$, which is regular.

Given a $|\Sigma|>1$, assume that $L=\{ ww^R|w\in\Sigma^*\}$ is regular and let $p$ be it's pumping length.

Consider the string $w^2(w^R)^2\in L$ where $|w|\geq 1$, $|ww|\leq p$ and $w\notin L$. This is all easily possible you chose a pumping length $p\geq 4$

Now write it as $xyz$ where $x=y=w$ and $z=(w^R)^2$.

Now pump up once to get $w^3(w^R)^2\in L$, which contradicts the definition of $L$.

We must therefore conclude that $L$ is not regular.

$\endgroup$
  • $\begingroup$ You aren't allowed to choose the $xyz$, because the content of the lemma says "there is a splitting $xyz$ such that...". What if there is another way to split it that does satisfy the lemma? (I don't think there is, but that does not make this a proof) $\endgroup$ – Henry Swanson May 8 '14 at 22:30
0
$\begingroup$

Assume that L is regular.
Consider any pumping lemma constant k (note: k is a positive integer so $k>=1$). Now consider a string s=$a^m$$b^m$$b^m$$a^m$ where $m>=1$

Now consider any decomposition of this string. It will be of the form $s=xyz$ where y will be of the form y = $a^j$ where $1<=j=k$ . Now by pumping lemma, $xv^ik$ belongs to L for all $i>=0$. Consider i=0, then we have the string of the form $a^lb^ma^mb^m$ where $l<m$. Since the number of a's in the left side of the string is less than the number of a's in the right part of the string, it can never be represented as $ww^R$ where $w∈${a,b}$^*$. So this violates our assumption that L is regular

We have by contradiction that L is not regular

$\endgroup$

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.