Language equivalence - manipulation of languages with Star operator

73 Views Asked by At

Why is this always true $(A^{*} \cap B^{*})^{*} = (A \cap B)^{*}$ ?

$A^{*} = \{ x_{1}x_{2}...x_{k}| k \ge 0$ and each $x_{i} \in A\}$, and similarly for B.

Assuming A and B are any languages i.e. sets of strings.

1

There are 1 best solutions below

1
On BEST ANSWER

Perhaps I am missing something, but the result doesn't seem to be true.

Let $A = \{aa\}$, $B = \{aaa\}$. Then $A \cap B = \emptyset$. However, $A^* \cap B^* = \{ aaaaaa \}^*$ (and hence $(A^* \cap B^*)^* = \{ aaaaaa \}^*$).