Question

Consider the class of C of languages over {0,1}*such that L is in C if the complement of L is finite. For each of the following answer yes or no, thenjustify your answer.(Add more lines if necessary.) A sample language in C is the set of all bit strings other than 001 and 110. A sample language not in C is the set of all bit strings of even length.

a. Is C closed under intersection?
b. Is C closed under complementation
c. Is C closed under union?

Answer 1

a) Yes

b) No

c) Yes

Step-by-step explanation:

a) C is closed under intersection ( Yes )

To justify my answer lets consider two languages : C1 and C2 are in C

C1 ∩ C2 has a complement of C'1 ∪ C'2 which will be finite which shows that C will be closed under complement

B) C is not closed under complementation ( NO )

because Complement of C1 in language C is C'1 which will be finite while the complement of C'1 which is C1 is not finite hence C will not be closed under complementation

C) C is closed under union ( Yes )