Peter Linz Edition 4 Exercise 4.3 Question 24 (Page No. 124)

Question

Suppose that we know that $L_1 ∪ L_2$ and $L_1$ are regular. Can we conclude from this that $L_2$ is regular?

Answer 1

If L1 U L2 is regular and L1 is regular, then we cannot conclude that L2 is also regular.

Let L1 U L2= ∑* and L1 = ∑*
Then L2 ={ aⁿbⁿ |n>=0} is not regular and L1 U L2 is regular.

Answer 2

if L1 is regular and L1 U L2 is regular then we cannot conclude that L2 is regular ,

 L1=(a+b)* ,  L2={a^n b^n |n>0}    L1 U L2 = (a+b)*