Is the complement of $L = \{a^nb^mc^p \ , n= m= p\}$ a context free language.

I believe that we can write $L^{'} \ as \ L1 \cup L2$ where

$L1=(a^*b^*c^*){'} \ $

$L2={{a^nb^mc^p \ m\ne n \ or \ n\ne p }}$

Now L1 is context free. I do believe that L2 as context free. Since context free languages are closed under union $L'$ is context free.

However while giving an exam I marked this language as context free. In the answer key it is a wrong answer. Now either I am wrong or the answer key is wrong.

What is my mistake?

  • 2
    $\begingroup$ Have you seen prove the complement of a language is context free? $\endgroup$
    – mikeazo
    Dec 22, 2017 at 13:31
  • $\begingroup$ @mikeazo thanks for the reference. Regarding the answer given by Yuval to that question he has taken 3 cases: i!=j , j!=k and i!=k. I believe the 3rd the case is not required. Am I true? $\endgroup$ Dec 22, 2017 at 13:39
  • 2
    $\begingroup$ a=b=c is equivalent to a=b intersection b=c. If you complement the intersection of two conditions then you get a!=b union b!=c. $\endgroup$ Dec 22, 2017 at 14:12
  • $\begingroup$ @KishanKumar True. If we take a word with $n \neq p$, then we have either $n \neq m$ or $p \neq m$, because $m$ can't be equal to both $n$ and $p$. So two cases are sufficient. $\endgroup$
    – user80502
    Dec 22, 2017 at 14:28
  • $\begingroup$ You may try the pumping lemma for CFL here, if you take the string a^(n+n!)b^nc^(n+n!), I think you can't pump it, therefore, not CF. $\endgroup$ Jan 22, 2018 at 1:33


Your Answer

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

Browse other questions tagged or ask your own question.