HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
contextregularthenfree

Problem

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.

Solution

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$

Context

StackExchange Computer Science Q#128602, answer score: 3

Revisions (0)

No revisions yet.