3
$\begingroup$

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.

| cite | improve this question | |
$\endgroup$
  • 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$ – Dmitry Jul 22 at 9:13
  • 1
    $\begingroup$ In your example $A^* \cap a^*b^* = A$. That should help. $\endgroup$ – Hendrik Jan Jul 22 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 Jul 22 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$ – Yuval Filmus Jul 22 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$ – Hendrik Jan Jul 22 at 18:05
3
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ case closed :-) $\endgroup$ – Hendrik Jan Jul 22 at 16:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.