Help with figuring out if MAX(L) is a CF language

Question

We call the word $x_1$ a true prefix of the word $x$, if a non-empty word $x_2$ exists so that $x=x_1x_2$. For the language L (over some finite $abc$..). We define MAX(L) as:

$MAX(L)$ = {$w_1 \in L $| $w \notin L$ so that $w_1$ is a true prefix of $w$}

prove (or disprove): If the language L is CF then the language $MAX(L)$ is CF.

I think that the correct direction here is to disprove. The question is, how do I disprove it for a general $L$?

I know how to use the pumping lemma to disprove a certain language, but I'm not sure if it can work for a general $L$?

Am I going in the right direction or am I completely wrong?

Answer 1

Let $L = a^*b^*c^* \setminus \{ a^n b^n c^k : k > n \}$. To see that $L$ is context-free, note that we can write it as follows: $$ L = \{ a^n b^m c^k : n > m \} \cup \{ a^n b^m c^k : m > n \} \cup \{ a^n b^m c^k : k \leq n \}. $$ The only way in which a word in $L$ cannot be extended non-trivially into another word in $L$ is if the word is of the form $a^nb^nc^n$ for $n \geq 1$. Therefore $$ \mathrm{MAX}(L) = \{ a^n b^n c^n : n \geq 1 \}, $$ which is known to be non-context-free.