If a regular language only contains Kleene star, then is it possible that it comes from the concatenation of two non-regular languages?

Question

I want to know that given a regular language L that only contains Kleene star operator (e.g (ab)*), is it possible that L can be generated by the concatenation of two non-regular languages? I try to prove that L can be only generated by the concatenation of two regular languages.

Thanks.

Answer 1

This statement is false. Consider these two languages over Σ = {a}:

L₁ = { aⁿ | n is a power of two } ∪ { ε }

L₂ = { aⁿ | n is not a power of two } ∪ { ε }

Neither of these languages are regular (the first one can be proven to be nonregular by using the Myhill-Nerode theorem, and the second is closely related to the complement of L₁ and can also be proven to be nonregular.

However, I'm going to claim that L₁L₂ = a*. First, note that any string in the concatenation L₁L₂ has the form aⁿ and therefore is an element of a*. Next, take any string in a*; let it be aⁿ. If n is a power of two, then it can be formed as the concatenation of aⁿ from L₁ and ε from L₂. Otherwise, n isn't a power of two, and it can be formed as the concatenation of ε from L₁ and aⁿ from L₂. Therefore, L₁L₂ = a*, so the theorem you're trying to prove is false.

Hope this helps!