I am currently studying for my exam and I am having trouble to solve this question:

Right or wrong: If $A$ is context-free then $A^*$ is regular.

I think it's wrong because if $A$ is context-free it means that $A$ can be a non-regular language. And the non-regular languages are not closed under the Kleene star operation (at least I think so). I am not sure how write this in a more formal way.

Maybe like this?

Let $A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that $A$ is non-regular and context-free. However, I'm not sure what $A^*$ is.

  • 1
    $\begingroup$ For your example, $A$ means "balanced nested brackets" and $A^*$ means "balanced bracket sequence". Both are context-free and non-regular (you can prove that counting their residuals). $\endgroup$
    – user114966
    Commented Jul 22, 2020 at 9:13
  • 1
    $\begingroup$ In your example $A^* \cap a^*b^* = A$. That should help. $\endgroup$ Commented Jul 22, 2020 at 9:37
  • $\begingroup$ @HendrikJan How it that going to help me ? Please dont tell me the solution, maybe just a little hint. $\endgroup$
    – Frank
    Commented Jul 22, 2020 at 9:56
  • 1
    $\begingroup$ @Frank You know that $A$ is non-regular, that $a^*b^*$ is regular, and that $A^* \cap a^*b^* = A$, and want to deduce that $A^*$ is non-regular. $\endgroup$ Commented Jul 22, 2020 at 12:48
  • 1
    $\begingroup$ @Dmitry Perhaps it is interesting to note that the bracket sequences in $A^*$ do not comprise all nested sequences (or Dyck words). For instance $aababb$ is properly nested, but not covered by the star. $\endgroup$ Commented Jul 22, 2020 at 18:05

1 Answer 1


Let $A=\{a^nb^n \mid n \in \mathbb{N}\}$. Then we know that $A$ is non-regular and context-free. Also we can see that $A^*\cap a^*b^*=A$. Since $a^*b^*$ is a regular expression, we do know that it is regular. Lets assume that A* is regular.

The regular languagues are closed unter intersection. Therefore $A^*\cap a^*b^*$ must be also regular(because we assume that $A^*$ is regular). This would implicate that A is regular because $A^*\cap a^*b^*=A$. This is a contradiction because we know that A is not regular. Therefore A* cant be regular.


  • $\begingroup$ case closed :-) $\endgroup$ Commented Jul 22, 2020 at 16:06

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.