3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Fabio Somenzi
    Commented Dec 20, 2017 at 15:41

1 Answer 1

Reset to default
2
$\begingroup$

The problem with your solution:

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

  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

$\endgroup$
4
  • $\begingroup$ Thank you for the explanation. But I got stuck on this part Because of the two first conditions, all possible xyz divisions of s are in the following form: x=a^k y=a^m z=a^(p−m−k)ba^p How does he come to that conclusion? And also, is it always easier to consider the complement language or is it specific to this case? If so, how do you know when to consider the complement instead? $\endgroup$
    – automatatheoriesq
    Commented Dec 20, 2017 at 16:42
  • $\begingroup$ Is this correct? Let L = {w∈{a,b}^*:w=w^rev} Show that L is not regular. 1.a^n b a^n, n ∈ N belongs to L 2. Assume that L is regular. 3. Let N be given to L according to the pumping lemma 4. u=∈ w =a^n v=ba^n, so uwv=a^n b a^n and |w|>=N 5. Assume that w = xyz, y>0 Then uxy^2zv ∈ L, when y>0 y only contains a therefor there will be more a's before the b than after. 6. This is a contradiction to the pumping lemma -> L != regular Edit: Cant figure out how to format this correctly $\endgroup$
    – automatatheoriesq
    Commented Dec 20, 2017 at 17:31
  • $\begingroup$ @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. $\endgroup$
    – Ove Ahlman
    Commented Dec 21, 2017 at 6:40
  • $\begingroup$ It is both hard for you to write and fit the solution in this comment section, and for me to read it. Instead edit your question and add the new solution after the old. As it looks right now it is much better, but there are still weird things going on. If it was my exam you would probably score 3 points (or 2 at the very least) for that solution. Also how to format mathematics: math.stackexchange.com/help/notation $\endgroup$
    – Ove Ahlman
    Commented Dec 21, 2017 at 6:47

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .