0
$\begingroup$

Prove that the language $\{a^i b^j c^k $ $|$ $i>j>k \geq 0\}$ is non context free language without using the pumping lemma.

we could use some helpful facts to solve the question:

  1. $A$ is a context free language and $B$ is regular, then $ A \cap B $ is context free.
  2. $L_1$, $L_2$ are not context free languages, the intersection $L_1 \cap L_2$ is not context free as well.
$\endgroup$
  • 1
    $\begingroup$ The second helpful fact is wrong. Take two disjoint non-context-free languages. $\endgroup$ – Yuval Filmus Apr 11 at 17:38
  • $\begingroup$ if L1 is non context free language {a^i b^j c^k| i >=j>=k>=0} and L2 is non context free language {a^i b^j c^k| k>=j>=i >=0} the intersection of them is not context free $\endgroup$ – user102789 Apr 11 at 17:56
  • $\begingroup$ If $L_1 = L_2$ the helpful fact is also true. It's true for some pairs $L_1,L_2$, and false for others. I'd say that's not so helpful. $\endgroup$ – Yuval Filmus Apr 11 at 23:26
  • 1
    $\begingroup$ May I ask why you are interested in "without the pumping lemma"? Please explain, especially if you created this problem by yourself. Otherwise, can you provide a reference? $\endgroup$ – Apass.Jack Apr 12 at 3:56
  • $\begingroup$ there is a question in "Sipser" book about that, the question asked to prove the language is non-context-free language by using fact ( a context free language intersection regular language is context free language ). the question in chapter 2 question # 2.30 $\endgroup$ – user102789 Apr 12 at 4:29

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.