# If $A$ is context-free then $A^*$ is regular

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.

• 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). – Dmitry Jul 22 '20 at 9:13
• In your example $A^* \cap a^*b^* = A$. That should help. – Hendrik Jan Jul 22 '20 at 9:37
• @HendrikJan How it that going to help me ? Please dont tell me the solution, maybe just a little hint. – Frank Jul 22 '20 at 9:56
• @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. – Yuval Filmus Jul 22 '20 at 12:48
• @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. – Hendrik Jan Jul 22 '20 at 18:05

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.

$$q.e.d$$

• case closed :-) – Hendrik Jan Jul 22 '20 at 16:06