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?

  • $\begingroup$ Your definition is unclear. I assume you mean "$w \notin L$ for all $w$ such that $w_1$ is a true prefix of $w$". $\endgroup$ – Yuval Filmus Jun 15 '19 at 14:13
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ 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?) $\endgroup$ – Immanuel Jun 15 '19 at 15:06
  • $\begingroup$ Also, do I need to prove that the original $L$ is CF? or is the way we define L enough? $\endgroup$ – Immanuel Jun 15 '19 at 15:08
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jun 15 '19 at 15:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.