Solution p. lemma cfl exercise 8/01/25

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

by Giorgio Satta -
Number of replies: 0

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.