Is $L_2=\{w^*\,:\,w\in L_1\}$ where $L_1$ is regular, a regular language

automataformal-languagespumping-lemmaregular-language

Is language $L_2=\{w^*\,:\,w\in L_1\}$, where $L_1$ is regular, regular?

Intuitively it seems that it's not: the automaton accepting $L_2$ would most probably just be a loop made from an automaton accepting $L_1$ (it would accept a regular expression $L_1^*$). However, how would that automaton "remember" what was the last word read, and thus if all the repeating words all the same?

In other words it seems impossible to build an automaton that could tell $w_1\cdot w_1 \cdot w_1$ and $w_1 \cdot w_2 \cdot w_1$, for $w_1, w_2 \in L_1$ apart.

On the other hand, it seems impossible to proove that $L_2$ is not regular using the puming lemma – for $u \in L_2$, $u = w^n$, you could just pump $w$, and $u_2 = w^{n+k}\in L_2$

Best Answer

If $L_1$ is finite, then what you describe as $\{w^* : w\in L_1\}$ is regular. (See note 1 below for why this description is incorrect.)

But many regular languages are not finite, and for such a language, the above transformation does not always produce a regular language. (Although sometimes it does. If $L_1$ were $a^*$, then the transformed language would also be $a^*$.)

I don't think you'll be able to find a general proof using the pumping lemma, or in any other way, because the assertion is not always false; to show that it is not always true, you only need to find a single counter-example, which shouldn't be too difficult. But for a particular (non-finite) $L_1$, you should be able to prove non-regularity with the pumping lemma (if the result is in fact non-regular), because you can't "just pump $w$"; you can only pump up to $p$ symbols, and in a non-finite language there are $w$ whose length exceeds $p$.


Notes

  1. Although I think it's evident what you meant, what you wrote is not a description of a language. In mathematics, a language is a set of words. If $w$ is a word, $w^*$ is a language, which is to say that it's a set of words. $\{ w^* : w \in L_1\}$ is, therefore a set of sets of words which is very different from a set of words. So it's not a language at all; it's a different category of thing.

    $w^*$ means $\{ w^n : n \in \mathbb{N}\}$, and so your intended $L_2$ is $\{ w^n : w\in L_1, n\in \mathbb{N}\}$. Alternatively, as noted in a comment, you could write it as an infinite union: $\bigcup_{w\in L_1}w^*$

Related Question