How to prove that if a language A is not regular then A* isn't regular either?

I have tried the usual methods with no result.

  • 4
    $\begingroup$ What makes you think that this claim is correct? $\endgroup$ – Shaull Nov 4 '13 at 11:01
  • 3
    $\begingroup$ If you don't find a proof, look for a counter-example... $\endgroup$ – Denis Nov 4 '13 at 11:09
  • 1
    $\begingroup$ Hint: try a non-regular language over a unary alphabet $\{a\}$. See where that gets you. $\endgroup$ – Shaull Nov 4 '13 at 11:30
  • 2
    $\begingroup$ For Kleene star for a language over unary alphabet, see here. $\endgroup$ – Hendrik Jan Nov 4 '13 at 13:38
  • 2
    $\begingroup$ Actually, you don't even need to consider languages over a unary alphabet. Consider, for instance, non-regular languages containing at least all strings of length one over any alphabet. $\endgroup$ – Patrick87 Nov 4 '13 at 14:45

Hint: Suppose $L$ is any language over the alphabet $\Sigma$. If $L$ is not regular then so is $L+\Sigma$, yet $(L+\Sigma)^* = \Sigma^*$ is regular.

| cite | improve this answer | |
  • 1
    $\begingroup$ Excellent answer; although I fail to see how this is a hint, so much as a complete proof that the claim is false. $\endgroup$ – Patrick87 Nov 4 '13 at 19:31
  • $\begingroup$ @YuvalFilmus Does + mean union here? $\endgroup$ – T.... Nov 3 '15 at 20:43
  • $\begingroup$ @Turbo. That's right. $\endgroup$ – Yuval Filmus Nov 3 '15 at 20:55

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.