Define the complementary or (cor) of two languages by cor(L1, L2) = {omega : ome

Question

Define the complementary or (cor) of two languages by cor(L1, L2) = {omega : omega or omega } Show that the family or the regular languages is closed under the cor operation. 8-Exhibit an algorithm that, given any regular language L. determines whether or not L = L* Prove that the following languages are not regular. Find context-free grammars for the following languages (with n ge 0. m ge 0). L = {anbm: n le m + 3}. L = {w {a, b}* : an(w) ab(w)}. 13 - Show that the following grammar is ambiguous. S rightarrow aSbS|bSaS|lambda 6- Eliminate useless productions from S rightarrow a|aA|B|C, A rightarrow aB|lambda, B rightarrow Aa, C rightarrow cCD, D rightarrow ddd. 5-Convert the grammar S rightarrow AB|aB A rightarrow aaa|lambda, B rightarrow bbA into Chomsky normal form

Explanation / Answer

5.2

You prove that a grammar is ambiguous by showing different derivations for same input string.

Consider these two leftmost derivations for the string abab: 
S -> aSbS -> abS -> abaSbS -> ababS -> abab 
S -> aSbS -> abSaSbS ->abaSbS -> ababS -> abab 

Hence this grammar is ambiguous.

6. In the production rule for C, we keep generating a C always. It means that we dont erase a C. Therefore it is useless and the production rules S -> C and C -> cCD can be eliminated.

Also if you look at production rule for D, it can never be reached. So D -> ddd can also be eliminated.

PS: you should split the questions. 6 questions cant be 1 single question.

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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