Cheap and Secure Web Hosting Provider : See Now

[Solved]: Regular language concatenation with superset

, , No Comments
Problem Detail: 

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?

Asked By : yuri kilochek

Answered By : J.-E. Pin

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/20069

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback