The are some CFLs whose complements are not CFLs. This is equivalent to saying t

Question

The are some CFLs whose complements are not CFLs. This is equivalent to saying that there are some non-CFLs whose complements are CFLs. Let's show that the complement of the non-CFL a^n b^n c^n is a CFL. Here is grammar that describes the language a^n b^m, where n and m are different: Similarly, here is a grammar that describes the language b^n c^m, where n and m are different: Every string in the complement of a^nb^nc^n either: Contains "ba" Contains "ca" Contains "cb" Is of the form a^nb^mc* where n and m are different Is of the form a*b^nc^m where n and m are different Here's what you need to do: Make a grammar for the complement of a^nb^nc^n with start symbol S. Use the grammar rules given above. You are to give exactly five new rules (a rule with n alternatives counts as n rules). No more and no less. Explain why we don't have to consider the case a^nb*c^m where n and m are different. Be precise and concise.

Explanation / Answer

https://drive.google.com/file/d/0B_J0QWMNqFRmNlBjNnJEZnlna1U/view?usp=sharing

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

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