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:


*

*$x y^i z \in B$ for all $i \geq 0$.

*$|y| > 0$.

*$|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.
 A: The problem with your solution:


*

*You choose P = 4. I dont know what you tube videos you watch, maybe they do not actually do formal proof, or the y just want to display P for different numbers, but you cant choose P. The reason for this is that P represents (in some sence) the size of an arbitrary DFA (or rather a cycle in it) whose language is B. So what we do when we using pumping is that we show that there is no such DFA. When you assume P = 4 you directly assume that the DFA whose language is B has size 4... which is clearly not showing that no DFA of any size exists.

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

*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
