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

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?

• Your definition is unclear. I assume you mean "$w \notin L$ for all $w$ such that $w_1$ is a true prefix of $w$". – Yuval Filmus Jun 15 '19 at 14:13
• I think you are correct. I may have missed the translation a bit. The original translation is something like "There does not exists $w \in L$ so that ..." but it's sounds weird so I rephrased it. – Immanuel Jun 15 '19 at 15:03

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.
• Can this answer be used to correctly answer the question? even thought you are using $a,b,c$ (could I add w.l.o.g?) – Immanuel Jun 15 '19 at 15:06
• Also, do I need to prove that the original $L$ is CF? or is the way we define L enough? – Immanuel Jun 15 '19 at 15:08
• I attempted to present a context-free language $L$ such that $\mathrm{MAX}(L)$ isn't context-free. I'm not sure what my using $a,b,c$ has to do with it. Also, I gave a hint how to show that $L$ is context-free. – Yuval Filmus Jun 15 '19 at 15:53