# Regular language concatenation with superset

Let $A$ be some alphabet.

$A$ itself is a regular language.

$E = A^*$ is regular language over $A$. $E$ is a superset of all languages over $A$, regular or otherwise, i.e $E$ contains every possible string from symbols of $A$.

Now let $L$ be some regular language over $A$.

What is $\tilde{L} = L \cdot E$ ? More specifically, how $\tilde{L}$ and $E$ relate to each other? Are they equal? Is one subset of the other? Something else?

Source of the confusion is the following reasoning: closure under concatenation says that $\tilde{L}$ is a regular language and therefore $\tilde{L} \subseteq E$ (according to the above). On the other hand $\tilde{L}$ seems to contain strings $E$ does not, i.e. those that are formed by concatenating non-empty string from both languages.

Obviously this is wrong. What is going on here?

• $\tilde{L} \subseteq E$ holds trivially. Also, $\tilde{L} = E$ iff $\epsilon \in L$. I don't see why "obviously this is wrong"; also, what exactly are you referring to with "this"? – G. Bach Jan 29 '14 at 16:41
• @G.Bach to contradictions in my reasining – yuri kilochek Jan 29 '14 at 16:56
• It's probably more interesting to compare $L$ and $\tilde{L}$. – Raphael Jan 29 '14 at 17:17

There is a very simple answer to your question: the equality $LA^* = A^*$ holds if and only if $L$ contains the empty word.

Simply put, this statement of yours:

On the other hand $\tilde{L}$ seems to contain strings E does not, i.e. those that are formed by concatenating non-empty string from both languages.

is wrong.

As you say, $E$ contains every string containing only symbols from $A$. Since $L$ also only contains strings with symbols from $A$, $\tilde{L}$ must as well. Concatenating strings that have symbols only from $A$ will just get you another string whose symbols only come from $A$.

Your statement is flipped; it is $E$ that contains strings that $\tilde{L}$ may not.

• Suppose I take some non-empty string $s_1$ from $L$ and another one $s_2$ from $E$ and concatenate them $\tilde{s_2} = s_1 \cdot s_2$. $\tilde{s_2}$ might or might not lie in $E$. It it does, let us select $s_2 = \tilde{s_2}$ and repeat the process. It seems you imply that $\tilde{s_2} \in E$ always, for however many iterations. Is it true simply because $E$ is infinitely large and whatever string we take from it there is always a longer one? – yuri kilochek Jan 29 '14 at 17:12
• @yurikilochek $E$ contains all finite strings, so whatever two finite strings you concatenate, you'll always end up in $E$. The conceptual problem you're probably having is "if I do this infinitely many times, the string will be infinitely long". The problem with that is, what is "infinitely many times"? Every step of the iteration is only preceded by a finite number of steps, and so it only produces a finite string. – G. Bach Jan 29 '14 at 17:24