0
$\begingroup$

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$

$\endgroup$
1
  • $\begingroup$ This does not make sense: $w^*$ is a set, not a word. Do you mean $L_2 = \bigcup_{w \in L_1} w^*$ ? $\endgroup$
    – J.-E. Pin
    Commented Jun 19, 2022 at 11:51

1 Answer 1

2
$\begingroup$

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^*$

$\endgroup$
5
  • $\begingroup$ Same comment: $\{w^* \mid w \in L_1\}$ does not make sense. $\endgroup$
    – J.-E. Pin
    Commented Jun 19, 2022 at 12:00
  • $\begingroup$ @J.-E.Pin: of course, you're right. I was going to mention that, but it seemed like a side issue. $\endgroup$
    – rici
    Commented Jun 19, 2022 at 13:42
  • $\begingroup$ I agree with you that it is a side issue, but I think it is best not to leave incorrect wording on this site, which is consulted by many students. $\endgroup$
    – J.-E. Pin
    Commented Jun 19, 2022 at 16:29
  • $\begingroup$ @J.-E.Pin: how's that? $\endgroup$
    – rici
    Commented Jun 19, 2022 at 21:21
  • $\begingroup$ Perfect note!$\ $ $\endgroup$
    – J.-E. Pin
    Commented Jun 21, 2022 at 4:31

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .