# Is concatenation of regular language with any other language regular?

I came across following problem:

True or false? If $$L$$ is a regular and $$M$$ is not a regular language then $$L.M$$ is necessarily not regular.

Consider $$L$$ to be $$\emptyset$$ and $$M$$ be $$\{a^nb^n | n\leq 0\}$$
$$L.M=\emptyset$$, which is regular. Hence the statement is false.

I guess the solution incorrectly tries to generalize the case of those two specific languages to all other languages. For example, if $$M$$ is DCFL, then I believe $$L.M$$ wont be regular. Am I correct with this?

• The statement is "$L.M$ is necessarily not regular." A statement is false if there is a single counter-example, which that solution provides. No "generalisation" is involved. (Also, $M$ is a DCFL, so your conjecture is wrong.) – rici Dec 25 '19 at 18:30
• ohhh so, "is necessarily not regular" means "is not regular", whereas "not necessarily regular" means "may or may not be regular" (never came across word usage "necessarily not", it was always "not necessarily") – anir Dec 25 '19 at 18:35
• Yep. It means "is always (not regular)". – rici Dec 25 '19 at 18:39
• A more interesting version of this question is: for which languages $L$ is it the case that for all languages $M$, the language $LM$ is regular. – Yuval Filmus Dec 25 '19 at 23:50
• I meant exactly what I wrote. – Yuval Filmus Dec 26 '19 at 7:45

As you show, if $$L = \emptyset$$ then $$LM$$ is regular for any language $$M$$. Conversely, for languages over $$\{0,1\}$$ (or any non-unary alphabet), there is a language $$M$$ such that if $$L \neq \emptyset$$ then $$LM$$ is not regular: $$M = \{10^p : p \text{ prime}\}.$$ Indeed, suppose that $$w \in L$$. Then $$w^{-1}(LM \cap w10^*) = M.$$ Since all of the operations preserve regularity, we conclude that $$LM$$ is not regular.

Over a unary alphabet, the picture is a bit different. Let $$M = \{ 0^{n!} : n \geq 0 \}.$$ If $$L \neq \emptyset$$ is finite then $$LM$$ is not eventually periodic, and so not regular. If $$L$$ is infinite and not regular, then $$L\{\epsilon\}$$ is not regular. If $$L$$ is infinite and regular, then it is eventually periodic. For every language $$M$$, $$LM$$ is also eventually periodic (with the same period), and so regular.