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?

  • 1
    $\begingroup$ $\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"? $\endgroup$ – G. Bach Jan 29 '14 at 16:41
  • $\begingroup$ @G.Bach to contradictions in my reasining $\endgroup$ – yuri kilochek Jan 29 '14 at 16:56
  • $\begingroup$ It's probably more interesting to compare $L$ and $\tilde{L}$. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – yuri kilochek Jan 29 '14 at 17:12
  • 1
    $\begingroup$ @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. $\endgroup$ – G. Bach Jan 29 '14 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.