2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 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$
    – Kishan Kumar
    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$
    – Kishan Kumar
    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$
    – matheussilvapb
    Jan 22, 2018 at 1:33

0

Reset to default

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.