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.

Improve this question
$\endgroup$
8
  • 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$
    – user114966
    Jul 22 '20 at 9:13
  • 1
    $\begingroup$ In your example $A^* \cap a^*b^* = A$. That should help. $\endgroup$
    – Hendrik Jan
    Jul 22 '20 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 '20 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 '20 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 '20 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$

Improve this answer
$\endgroup$
1
  • $\begingroup$ case closed :-) $\endgroup$
    – Hendrik Jan
    Jul 22 '20 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.