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.
2
$\begingroup$
$\endgroup$
-
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
1
$\begingroup$
$\endgroup$
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.
answered Nov 4 '13 at 16:45
-
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
-
-
