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

Hint:

For regular languages, operations such as complement, union, and intersection preserve regularity, while non-regular languages may not guarantee these properties.

Answer 1

The Correct Option is C

Step 1: Analyze \( L_1 = L_2 \) condition.
For \( L_1 = L_2 \), the condition \( L_1 \cap \overline{L_2} = \phi \) must hold. However, this is not a sufficient condition to prove equality, so statement (1) is false. Step 2: Analyze \( L_1 \cup L_3 \).
If \( L_3 \) is non-regular, \( L_1 \cup L_3 \) may or may not be non-regular, depending on \( L_3 \). Hence, statement (2) is false. Step 3: Analyze \( L_3 \).
Since \( L_3 \) is given as non-regular, statement (3) is true. Step 4: Analyze \( \overline{L_1} \cup \overline{L_2} \).
The complement and union of two regular languages are regular. Thus, \( \overline{L_1} \cup \overline{L_2} \) is regular, making statement (4) true. Final Answer: \[ \boxed{\text{(3) and (4)}} \]