We have seen in class that the sets of both regular and context-free languages are closed under the union, concatenation, and st
ar operations. We have also seen in A2 that the regular languages are closed under intersection and complement. In this question, you will investigate whether the latter also holds for context-free languages.
(a) Use the languages A = {a^mb^nc^n \ m, n greaterthanorequalto 0} and B = {a^nb^nc^m \ m, n greaterthanorequalto 0} to show that the class of context-free languages is not closed under intersection. You may use the fact that the language C = {a^nb^nc^n | n greaterthanorequalto 0} is not context-free.
(b) Using part (a) above, show now that the set of context-free languages is not closed under complement.
(a) Use the languages A = {a^mb^nc^n \ m, n greaterthanorequalto 0} and B = {a^nb^nc^m \ m, n greaterthanorequalto 0} to show that the class of context-free languages is not closed under intersection. You may use the fact that the language C = {a^nb^nc^n | n greaterthanorequalto 0} is not context-free.
(b) Using part (a) above, show now that the set of context-free languages is not closed under complement.
1 answer:
You might be interested in