in Theory of Computation edited by
2,533 views
3 votes
3 votes

Given the following statements:

  1. A class of languages that is closed under union and complementation has to be closed under intersection
  2. A class of languages that is closed under union and intersection has to be closed under complementation

Which of the following options is correct?

  1. Both (i) and (ii) are  false
  2. Both (i) and (ii) are true
  3. (i) is true, (ii) is false
  4. (i) is false, (ii) is true
in Theory of Computation edited by
2.5k views

1 comment

A intersection  B  = (A'UB')'  . since set is closed under complement and union   so it must be closed  under intersection  so a is true  ( union and complement-> intersection

no such relation between union , intersection  --> complementation
0
0

7 Answers

2 votes
2 votes

Based on the above closure properties,

(A) is TRUE. Because Regular Languages are an example of being closed under union and complementation, and thus under intersection.

(B) is FALSE. Because Recursively Enumerable Languages are closed under both union and intersection but NOT under complementation.

 

1 vote
1 vote
Here we can derive this statement with the help of closure properties

S1: true as it is the case for  Regular grammar

S2:false, as in RE language it is closed under Union,Intersection but not in complementation'

so 3 is correct answer here

1 comment

just by taking exmaple of regular we can't conclude S1 is true , we need  to check for CSL and REC too
0
0
1 vote
1 vote
0 votes
0 votes
Here we can derive this statement with the help of closure properties

S1: true as it is the case for  Regular grammar

S2:false, as in RE language it is closed under Union,Intersection but not in complementation'

so 3 is correct answer here
Answer:

Related questions