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