Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular? By the way, L is a fixed language in the problem that I am solving, but it's regularity is trivial to prove so I have omitted it. This next step, however, I can't think of a valid way to prove. I would be glad if you guys could give me a hint.


Your language is known as $L^+$.

It is a very standard property of regular languages that if $L$ is regular then so is $L^*$; this can be proved in several ways, and you can find proofs in textbooks and online sources. Since $L^+$ is either equal to $L^*$ or obtained from it by removing $\epsilon$ (the empty string), then $L^+$ is also regular.

  • $\begingroup$ Oh god. I was looking at some more complex constructions the whole day and been overthinking it. Thank you! $\endgroup$
    – arnaudoff
    Jun 20 '19 at 11:16

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.