Does concatenating a language with Σ* always result in the universal language?

Question

I'm trying to understand how language concatenation works with the universal language (i.e., Σ*). Suppose I have a language like L = {an}, and I concatenate it with the universal language. For example:

L . Σ* (like an . (a+b)*)

Σ* . L (like (a+b)* . an)

Will the result always be the universal language in both cases? Or are there cases where it won't be? I’d appreciate a simple explanation

Answer 1

No, it won't. This only holds for languages $L$ that contain the empty word $\epsilon$. Then $\Sigma^\ast \subseteq L \cdot \Sigma^\ast$, since any word $w$ can be written as $\epsilon \cdot w$. For any language we have $L'\subseteq\Sigma^\ast$, so that $L\cdot\Sigma^\ast = \Sigma^\ast$.

Suppose that $L$ is a language that does not contain the empty word. Then any word in $L\cdot\Sigma^\ast$ cannot be the empty word either as it has a minimum length of the shortest word in $L$, which is longer than the empty word.

Whether this holds for your example depends on the restrictions placed on $n$.

• Dev Ops: If L is regular, will this work?
• jt0202: No, as not every regular language contains the empty word. $L = \{a\}$ is regular, but $L \cdot \Sigma^\ast$ does not contain the empty word as every word starts with a.

Answer 2

No, the simplest counter-example is the language {a}, this will then enforce that you start or end a string with a. If the universal language has a and b, it thus can no longer work with bb for example.

If your language has only one character, adding {a} requires the strings to be at least one character long, whereas Σ* also includes the empty language.