8. (6 points) Pove that the CFLs are not closed under complementation, i.c., it is possible...

Transcribed Image Text:

8. (6 points) Pove that the CFLs are not closed under complementation, i.c., it is possible that A is not a CFL for a CFL A, where A is the complement of A (if needed, review the definition of complement in Question 1 of Homework 2). Hint: We have shown in class that CFLs are not closed under intersection. Prove by contra- diction that if CFLs were closed under complementaion then CFLs would also be closed under intersection. You may also find DeMorgan's law useful, i.e., for two sets A and A2, it holds that A U A = A A (the complement of the union of two sets A and A is equal to the intersection of the complements of A and A). 9. (6 points) In class, we proved that the intersection of a CFL and a regular language is still a CFL. Using this property and the fact that the language {abcm |0 mn} in Question 7(b) is not context free, prove that the following language A is not context free. A = {w | w *, and in w, the number of a's is equal to the number of b's and is larger than or equal to the number of c's}, where = {a, b, c}. For example, both aabcb and cba are in A, but neither baac nor accb is in A. 8. (6 points) Pove that the CFLs are not closed under complementation, i.c., it is possible that A is not a CFL for a CFL A, where A is the complement of A (if needed, review the definition of complement in Question 1 of Homework 2). Hint: We have shown in class that CFLs are not closed under intersection. Prove by contra- diction that if CFLs were closed under complementaion then CFLs would also be closed under intersection. You may also find DeMorgan's law useful, i.e., for two sets A and A2, it holds that A U A = A A (the complement of the union of two sets A and A is equal to the intersection of the complements of A and A). 9. (6 points) In class, we proved that the intersection of a CFL and a regular language is still a CFL. Using this property and the fact that the language {abcm |0 mn} in Question 7(b) is not context free, prove that the following language A is not context free. A = {w | w *, and in w, the number of a's is equal to the number of b's and is larger than or equal to the number of c's}, where = {a, b, c}. For example, both aabcb and cba are in A, but neither baac nor accb is in A.

Answer rating: 100% (QA)

Solutions Step 1 Lets address both questions step by step Question 8 Proving that CFLs are ... View the full answer