Solution p. lemma cfl exercise 8/01/25

Solution p. lemma cfl exercise 8/01/25

by FRANCESCO VEZZANI -
Number of replies: 4

In this exercise done in class during lecture of 8/01/2025 the applying of pumping lemma was left as exercise at home. I have a doubt if my solution correct, in particular I’m not sure of the second case I provide for factorization where  v has some a’s and x has some b’s. 


Thank you 

Exercise

In reply to FRANCESCO VEZZANI

Re: Solution p. lemma cfl exercise 8/01/25

by Giorgio Satta -
I have noticed a glitch in your paperwork: In the pumping lemma conditions, you should have \( vx \neq \varepsilon \), not \( v,x \neq \varepsilon \): the two conditions have different meaning.

Case 2 in the application of the pumping lemma is ok, but you are stating \( |v| =m \), \(|x| = m \): there is no such condition in the pumping lemma. The length of \( v,x \) do not need to be equal, the only thing we know is \( |vx| > 0 \).

Finally, one case is missing in the application of the pumping lemma. You need to discuss the case in which one among \( v, x \) falls across two consecutive blocks.
In reply to Giorgio Satta

Re: Solution p. lemma cfl exercise 8/01/25

by FRANCESCO VEZZANI -
Thank you very much professor Satta. 1. My first mistake comes from my misunderstanding of the condition vx different from epsilon, what is not clear to me is how they can be considered together when I have the symbol w in between. 2. This second issue it’s also related to the misunderstanding of how I can have condition vx differ from epsilon if I have w in between the two. 3. For the missing case can i consider just across a and b and b and c in a single case or i have to manage in two separate cases? I was thinking of demonstrating it using k=0 is it right ? Thank you very much
In reply to FRANCESCO VEZZANI

Re: Solution p. lemma cfl exercise 8/01/25

by Giorgio Satta -

It is certainly true that \( v, x \) do not appear together inside the string \( w \) that you have chosen. However writing \( |v x| > 0 \) simply means that there is at least one alphabet symbol occurring in \( v \) or in \( x \), but you do not know exactly which one of the two.

As for the missing case, if \( v \) or \( x \) simultaneously contains occurrences of \( a \) followed by occurrences of \( b \), then you should use \( k > 2 \). In this way you will get occurrences of \( b \) followed by occurrences of \( a \), and the resulting string cannot be in the language. The case in which \( v \) or \( x \) simultaneously contains occurrences of \( b \) followed by occurrences of \( c \) is similar.

I hope this is clear. If not, you should ask for office hours.