contestada

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?

Respuesta :

batolisis

Answer:

a)  Yes

b) No

c) Yes

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 )

Otras preguntas