Show that context-free languages are not closed under setdifference. That is, sh

Question

Show that context-free languages are not closed under setdifference. That is, show that the language L1 - L2 is not necessarily context-free even whenboth L1 and L2 are. Do this by constructing two specific context-free languages, L1 and L2,such that the language L1 ¡ L2 is demonstrably non-context-free.
I know we have to use the pumping lemma for context freelanguages, but I don't even know where to start on defining thelanguage for L1 and L2. Show that context-free languages are not closed under setdifference. That is, show that the language L1 - L2 is not necessarily context-free even whenboth L1 and L2 are. Do this by constructing two specific context-free languages, L1 and L2,such that the language L1 ¡ L2 is demonstrably non-context-free.
I know we have to use the pumping lemma for context freelanguages, but I don't even know where to start on defining thelanguage for L1 and L2.

Explanation / Answer

Dear User, Let L1 = axbycy      where x,y >=0 , iscontext free       L2 = aybycx    where x,y >=0, is context free Then L1 – L2 =axb0cy                  =axcy     x,y>=0 and x!= y, Which is not context free. ITS HELPFUL TO YOU.... ITS HELPFUL TO YOU....

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.