subject

We have seen in class that the sets of both regular and context-free languages are closed under the union, concatenation, and star 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.

ansver
Answers: 1

Other questions on the subject: Computers and Technology

image
Computers and Technology, 22.06.2019 06:30, gracie2492
What result from the passage of this amendment
Answers: 1
image
Computers and Technology, 22.06.2019 17:50, ImBADatmath8743
Farah works in an office with two other employees. all three share a printer and an internet connection. the utility that makes this possible is defragger quicktime soho winzip
Answers: 1
image
Computers and Technology, 23.06.2019 02:30, jalaholmes2027
Three out of five seniors remain undecided about a college major at the end of their senior year.
Answers: 3
image
Computers and Technology, 23.06.2019 22:30, keel5468
You draw two cards from a standard deck of 52 cards, but before you draw the second card, you put the first one back and reshuffle the deck. (a) are the outcomes on the two cards independent? why?
Answers: 3
You know the right answer?
We have seen in class that the sets of both regular and context-free languages are closed under the...

Questions in other subjects:

Konu
Mathematics, 16.09.2021 09:30
Konu
Chemistry, 16.09.2021 09:30
Konu
Mathematics, 16.09.2021 09:30
Konu
Mathematics, 16.09.2021 09:30
Konu
Mathematics, 16.09.2021 09:30