Question

Give examples of languages L1 and L2 over {a, b} that satisfy the descriptions below:

(a) L1 is regular, L2 is nonregular, and L1 U L2 is regular;

(b) L1 is regular, L2 is nonregular, and L1 U L2 is nonregular;

(c) L1 is regular, L2 is nonregular, and L1 n L2 is regular;

(d) L1 is nonregular, L2 is nonregular, and L1 U L2 is regular.

(e) L1 is nonregular, L2 is nonregular, and L1 n L2 is regular.

Answer 1

(a) L1 = a* , L2 = a^n such that n is prefect square. L1 U L2 is a* which is regular

(b) L1 = aa , L2 = a^n such that n is prefect square. L1 U L2 is L2 which is non regular

(c) L1 and L2 same as above.  L1 intersection L2 is L1 which is regular.

(d) L1 = (a^n)(b^m ) where n>=m, L2= (a^n)(b^m ) where n<=m both are not regular L1UL2 is a*b* which is regular.

(e) L1 = a^n such that n is not divisible ny 3, L2 = a^n such that n is divisible ny 3, So L1 intersection L2 is null set which is regular.