2
$\begingroup$

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.

$\endgroup$
10
  • 4
    $\begingroup$ What makes you think that this claim is correct? $\endgroup$
    – Shaull
    Nov 4, 2013 at 11:01
  • 3
    $\begingroup$ If you don't find a proof, look for a counter-example... $\endgroup$
    – Denis
    Nov 4, 2013 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, 2013 at 11:30
  • 2
    $\begingroup$ For Kleene star for a language over unary alphabet, see here. $\endgroup$ Nov 4, 2013 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, 2013 at 14:45

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • 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, 2013 at 19:31
  • $\begingroup$ @YuvalFilmus Does + mean union here? $\endgroup$
    – Turbo
    Nov 3, 2015 at 20:43
  • $\begingroup$ @Turbo. That's right. $\endgroup$ Nov 3, 2015 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.