Prove or disprove the following statements a If L1 and L2 ar

Prove or disprove the following statements.

(a) If L₁ and L₂ are non-regular languages, then L₁ L₂ is also non-regular.

(b) If L₁ is a regular language and L₂ is a non-regular language, then L₁L₂ is regular

Solution

a. If L1 and L2 are nonregular languages, then L1 L2 is also not regular.

False.

Let L1 = {aⁿ b^m, n m} and L2 = {aⁿ b^m, n m}. L1 L2 = a*b*, which is regular.

To prove it, we offer a counter example. Let L1 = {aⁿ b^m : n=m} and let L2 = {anⁿb^m : n m}. We have shown that both L1 and L2 are not regular. However, L1 L2 = a*b*, which is regular. There are plenty of other examples as well. Let L1 = {an : n 1 and n is prime}. Let L2 = {an : n 1 and n is not prime}. Neither L1 nor L2 is regular. But L1 L2 = a+ , which is clearly regular.

b.

If L1 regular and L2 are nonregular languages, then L1 L2 is also not regular. False. Let L1 = {aⁿb^m, n m} and L2 = {aⁿb^m, n m}. L1 L2 = a*b*, which is regular.