Given the following statements : (A) A class of languages that is closed under union and complementation has to be closed under intersection. (B) A class of languages that is closed under union and intersection has to be closed under complementation. Which of the following options is correct ?
(A) is true, (B) is false.
Closure questions of this kind are settled by set identities (to prove a statement) and by a counterexample class (to refute one).
(A) By De Morgan’s law, \(L_1 \cap L_2 = \overline{\overline{L_1} \cup \overline{L_2}}\). If the class is closed under complementation and union, every step on the right stays inside the class, so it is closed under intersection. (A) is true.
(B) Take the class of all finite languages over {a}. The union and the intersection of two finite languages are finite, so the class is closed under both, yet the complement of a finite language over {a} is infinite and leaves the class. Closure under union and intersection therefore does not force closure under complementation. (B) is false.
So (A) holds and (B) fails; the choices calling both true, both false, or only (B) true contradict these two arguments.
(A) is true, (B) is false. option is correct.
Similar Questions
Match the following :
List – I List – II a. Context free grammar i. Linear bounded automaton b. Regular grammar ii. Pushdown automaton c. Context sensitive grammar iii. Turing machine d. Unrestricted grammar iv. Deterministic finite automaton Codes :
a b c d
Given the recursively enumerable language (\(L_{RE}\)), the context sensitive language (\(L_{CS}\)), the recursive language (\(L_{REC}\)), the context free language (\(L_{CF}\)) and deterministic context free language (\(L_{DCF}\)). The relationship between these families is given by
The family of context sensitive languages is __________ under union and __________ under reversal.
Match the LIST-I with LIST-II
LIST-I LIST-II A. Type - 0 grammar I. Linear Grammar B. Type - 1 grammar II. GNF C. Type - 2 grammar III. x→y, |x|<|y|; x, y ∈ {V ∪ T}* D. Type - 3 grammar IV. Recursively Enumerable Choose the correct answer from the options given below:
Arrange the following Language Classes in ascending order according to their expressive power, as defined by Chomsky hierarchy :
(A) Context-free languages
(B) Context-sensitive languages
(C) Regular languages
(D) Unrestricted Grammars
Choose the correct answer from the options given below :
Which of the following is ε-free grammar?
Which of the following pairs have different expressive power ?
Important Questions from Automata Theory Concepts - Teaching
- Which of the following is FALSE ?
- Match List I with List II
List I List II A. Type 3 Grammar I. V $\rightarrow$ (V $\cup$$\Sigma$)* B. Type 2 Grammar II. $\lambda$V$\beta$ $\rightarrow$ $\lambda$(V $\cup$$\Sigma$)*$\beta$, where ($\lambda$,$\beta$)$\epsilon$(V $\cup$$\Sigma$)* C. Type 1 Grammar III. (V $\cup$$\Sigma$)* $\rightarrow$ (V $\cup$$\Sigma$)* D. Type 0 Grammar IV. V $\rightarrow$ V$\Sigma$|$\Sigma$
Choose the correct answer from the options given below: Match the following :
List – I List – II a. Context free grammar i. Linear bounded automaton b. Regular grammar ii. Pushdown automaton c. Context sensitive grammar iii. Turing machine d. Unrestricted grammar iv. Deterministic finite automaton Codes :
a b c d
Given the recursively enumerable language (\(L_{RE}\)), the context sensitive language (\(L_{CS}\)), the recursive language (\(L_{REC}\)), the context free language (\(L_{CF}\)) and deterministic context free language (\(L_{DCF}\)). The relationship between these families is given by
The family of context sensitive languages is __________ under union and __________ under reversal.
