patternMinor
If $A$ is context-free then $A^*$ is regular
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.
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$
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.