Consider the following statements. I. If L1 ∪ L2 is regular, then both L1 and…
2020
Consider the following statements.
I. If L1 ∪ L2 is regular, then both L1 and L2 must be regular.
II. The class of regular languages is closed under infinite union.
Which of the above statements is/are TRUE ?
- A.
Ⅰ only
- B.
Ⅱ only
- C.
Both Ⅰ and Ⅱ
- D.
Neither Ⅰ nor Ⅱ
Attempted by 163 students.
Show answer & explanation
Correct answer: D
Answer: Neither statement is true.
Why the first statement is false: If L1 ∪ L2 is regular it does not force L1 and L2 to be regular. Example: take L2 = Σ* (regular) and let L1 be any non-regular language. Then L1 ∪ L2 = Σ* is regular, although L1 is not.
Why the second statement is false: Regular languages are not closed under arbitrary (countably infinite) unions. Example: for each n ≥ 0 let L_n = {a^n b^n}, a finite (hence regular) language. The union ⋃_{n≥0} L_n = {a^n b^n | n ≥ 0} is a known non-regular language.
Therefore neither statement holds in general.