Prove/disprove: If $𝐿_1$ is a finite language but not empty and $𝐿_2$ is NOT regular then $𝐿_1 \circ 𝐿_2$ is NOT regular

Question

That what I have so far, but I am not sure at all.

Assume toward contradiction that $𝐿_1 \circ 𝐿_2$ is regular.

Define $\Sigma' = \{\sigma'|\sigma\in\Sigma\} $.

Define a regular substitution $\forall\sigma\in\Sigma, h(\sigma) = \sigma'$.

$h(𝐿_1) = \{𝑤 = 𝜎'_1𝜎'_2 ... 𝜎'_𝑛 | 𝑤 = 𝜎_1𝜎_2 ... 𝜎_𝑛 \in 𝐿_1\}$ is also regular and finite by the closure of RL under substitution.

Therefore, by the assumption $h(𝐿_1) \circ 𝐿_2$ is also regular. Define regular substitution $\forall\sigma'\in\Sigma',g(\sigma')=\varepsilon,\forall\sigma\in\Sigma,g(\sigma)=\sigma$.

$g(h(L_1) \circ 𝐿_2) = 𝐿_2$ which is regular by the closure of RL under substitution, in contradiction to the assumption. Therefore, $𝐿_1 \circ 𝐿_2$ is not regular. Q.E.D

I am not sure about this statement "$h(𝐿_1) \circ 𝐿_2$ is also regular".

Thanks for any help!!

Answer 1

$L_1\circ L_2$ can certainly still be non-regular. For example, when $L_1$ contains exactly one word.

However, $L_1\circ L_2$ can be regular, too. Here is an example. Let $L_1=\{\epsilon,0\}$. Let $L_2$ be the complement of $\{ 0^n1^n \mid n \gt 0 \}$. As the complement of a non-regular language, $L_2$ is not regular while $L_1\circ L_2$, the set of all words over $\{0,1\}$, is regular.

---

Here are three similar exercises.

Exercise 1. Construct examples when the alphabet contains exactly one letter.

Exercise 2. Prove or disprove: If $L_1$ is a finite language but not empty and $L_2$ is not context-free, then $L_1\circ L_2$ is not context-free.

Exercise 3. Prove or disprove: If $L_1$ is a finite language but not empty and $L_2$ is not recursive, then $L_1\circ L_2$ is not recursive.