0
$\begingroup$

I know that the Kleene star of an intersection is contained in the intersection of Kleene stars, but are they necessarily equal?

For example, given two formal languages, $A$ and $B$, I know that $(A\cap B)^*\subseteq A^*\cap B^*$, but does $(A\cap B)^*= A^*\cap B^*$?

$\endgroup$
  • $\begingroup$ I know it is contained but is it equal =? $\endgroup$ – drugsrbad Sep 26 at 21:04
4
$\begingroup$

Clearly not.

Let $A=\{a\}$ and $B=\{aa\}$.

Now,

$A\cap B = \emptyset$

so

$(A\cap B)^* = \{\epsilon\}$

but

$A^*\cap B^*=B^*=\{a^{2i} : i \in \mathbb{N}\}$

(all strings consisting of an even number of $a$).

$\endgroup$
  • $\begingroup$ @ttnick: Sorry, I should have gone for "accept and improve". Thanks for bringing this to my attention. $\endgroup$ – rici Sep 30 at 7:29

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.