Pumping lemma for regular language

On an exam we got this question:

Let $B = \{w \in \{a,b\}^* : w \neq w^{rev}\}$ Prove $B$ is not regular.

I only got 1 of 4 pts on this question and the teachers comments are below.

My solution:

Assume $B$ is regular then $B$ has a pumping length $P$ such that there is a string $S$, $|S| \geq P$. $S$ can be divided into $xyz$ and these 3 conditions will still hold:

1. $x y^i z \in B$ for all $i \geq 0$.
2. $|y| > 0$.
3. $|xy| \leq P$.

If we got the string $S = abbaab$ We assume $S$ is a regular language with pumping length $P = 4 \rightarrow S=a^4 b^4 b^4 a^4 a^4 b^4 = aaaabbbbbbbbaaaaaaaabbbb$

Teacher: "The word should depend on $P$, you can't choose $P$!"

Case 1: $Y$ contains only $a$ $\rightarrow x=aaaabbbbbbbb ~ y= aaaa ~ z=aaaabbbb$

Teacher: "You don't know how many $a$'s for example $a^P b^P$ ... etc"

For $i = 2$ we get $x=aaaabbbbbbbb ~ y=aaaaaaaa ~ z=aaaabbbb$

Teacher: "You need to know that $x y^i z$ becomes a palindrome for some $i$."

And I also had one case for only $b$ and one case for $a + b$. But they have the same problem.

Can someone explain what went wrong? When I've watched youtube videos about pumping lemma they all put some value in $P$ to get the string but apparently that's not allowed.

I know I should ask the teacher but I have an exam tomorrow so I won't be able to get an answer in time.

• The key point in applying the pumping lemma is to assume that there is some $P$, but you don't know what it is. I haven't seen those videos, but is it possible that they are just trying to help the viewer build up intuition by saying, "suppose $P$ were $3$, then..."? Since your language contains strings of arbitrary length, you can find the right word no matter what $P$ is. Dec 20 '17 at 15:41

2. When using the pumping lemma you can choose the string, but you can not choose how the string is divided. Thus when you write $y= aaaa$ you assume that there are exactly $4$ a in $y$. What about the case 3 or 1 $a$? You need to consider exactly all cases. This is why it is easier to do this a bit more general, and consider substrings like $y=a^i$ or $y=b^ja^i$, for some number $i,j$, instead of taking very specific substrings like you have done.
3. What we aim to show in the pumping proof is that when you pump with the choosen $i$, the string does not stay in the language. Thus what you need to do after choosing $i$ is to actaully proove that the resulting string will not be in the language ( and in your case I think it actually will be in the language and thus you have not proven anything).
A Proper solution: Note that $B$ is regular if and only if $B^c$ (the complement language) is regular. It is much easier to consider $B^c$, thus we can show that this language is not regular in order to solve the excersise instead. Clearly $B^c$ is the palindrome language. A proof of this can be found Here as one of the answers
• @automatatheoriesq a) he has the division $x=a^k, y=a^m,z=a^{p-m-k}ba^p$ since we know that $xy$ has to be the first block of the string and this block consists of at most $p$ characters ($|xy|<p$) together with the fact that the string starts with $p$ number of a:s. b) When to consider the complement language or not is a tricky question. I would say that this is just one of the many tools which you should keep in mind. If you dont succeed in pumping, then try switching to complement language. Dec 21 '17 at 6:40