GATE CSE 2024 | Set 1 | Question: 13

Question

​Let $L_1, L_2$ be two regular languages and $L_3$ a language which is not regular.

Which of the following statements is/are always TRUE?

• A. $L_1=L_2$ if and only if $L_1 \cap \overline{L_2}=\phi$
• B. $L_1 \cup L_3$ is not regular
• C. $\overline{L_3}$ is not regular 
• D. $\overline{L_1} \cup \overline{L_2}$ is regular

Answer 1

A is wrong

As double implication we need to check both sides and take a case where L1 is subset of L2 still intersection of the statement will be null.

Option B is wrong

because, take L1 as (a+b)*, now union of any non-regular language over alphabet a and b will always be regular.

Correct answers:

C and D

C is trivial and D is closure property where Regular languages are closed under both compliment and union.