0
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • 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
    Commented Jan 29, 2014 at 16:41
  • $\begingroup$ @G.Bach to contradictions in my reasining $\endgroup$
    – yuri kilochek
    Commented Jan 29, 2014 at 16:56
  • $\begingroup$ It's probably more interesting to compare $L$ and $\tilde{L}$. $\endgroup$
    – Raphael
    Commented Jan 29, 2014 at 17:17

2 Answers 2

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 29, 2014 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
    Commented Jan 29, 2014 at 17:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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