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

Question

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.

Frank · Answer

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$

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

One Answer

Add your own answers!

Ask a Question