Given L1 context free non regular language. Given L2 regular language.
Is it possible that L1 U L2 = regular language ? Also, is it possible that L1*L2 = regular language ?
I think that the 2nd one is impossible. But I'm not sure.
Would love to see an example if one of the abovementioned statements (or both) is/are true.
Is it possible that
L1 U L2
= regular language ?
Yes, Possible.
A simple case is: if L1 is sub-set of L2 then L1 U L2
will be regular (=L2
), for example: L1 : { anbn
| where n >= 0
} and L2 = (a + b)*
is it possible that
L1 * L2
= regular language ?
No, Concatenation of a context-free and Regular will be context-free (because constraint in pattern of L1 is still there in L1 * L2
).
Adding a reference: CS 273: Closure Properties for Context-Free Languages