regular-languagefinite-automataautomatacontext-free-language

concatenation & union - regular and context free languages


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.


Solution

  • 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