computer-sciencecontext-free-grammarregular-languagechomsky-normal-form

Is concatenation of a non regular language with a regular language always not regular?

I'd like to know if the concatenation between two language (one regular and the other not) is always not regular or it may happen that the output is a regular language. Thanks.

Solution

  • No, because we can find a counterexample that prove that sometimes it happen:

    L1 not regular: (a^2)^n with n>=0
    L2 regular: a*

    The concatenation produce the language L3= aa* and this is obviously regular.