I am working on some set theory and am trying to prove how a set can have the property $A^* = A$.

For set $A=\{0^n1^n \mid n \ge0\}$, I still do not understand exactly what $A^*$ is. For example, I thought $A^*$ is the enumeration of the set $A$ so

$A^* = \{\epsilon,01,0011,000111,00001111,....\}$

Any helping in at least understanding what $A^*$ is for this problem would be much appreciated!

  • $\begingroup$ $\{0^n1^n \mid n \ge0\}$ is exactly $\{\epsilon,01,0011,000111,00001111,\cdots\}$. $\endgroup$ – John L. Jan 29 '19 at 1:19
  • $\begingroup$ Can you confirm $A^*$ is the Kleenen star of $A$ in the question? $\endgroup$ – John L. Jan 29 '19 at 1:21
  • 1
    $\begingroup$ Your set doesn't satisfy $A^*=A$. $\endgroup$ – Yuval Filmus Jan 29 '19 at 4:57
  • $\begingroup$ If you are searching from some set $A$ satisfying $A=A^*$, try choosing $A=B^*$ for any $B$. Further, not all sets $A$ satisfy $A=A^*$, e.g. $A=\{0\}$ is surely different from $A^* = \{\epsilon,0,00,\ldots\}$. $\endgroup$ – chi Jan 30 '19 at 11:46

What you have written (i.e., $\{ \varepsilon, 01, 0011, 000111, \ldots \}$) is simply $A$ itself.

(Assuming $A^\ast$ is the Kleene star operation) you cannot prove $A = A^\ast$ because it is not correct.

The Kleene star $A^\ast$ is defined as the union of the powers $A^i$, where $A^0 = \{ \varepsilon \}$ and $A^{i+1} = A^i \cdot A = \{ w \cdot w' \mid w \in A^i, w' \in A \}$. An inductive argument easily shows: $$A^i = \{ w_1 \cdots w_i \mid w_1, \ldots, w_i \in A \} = \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid n_1, \ldots, n_i \ge 0 \}$$

Since $A^\ast$ is the union over all such $A^i$, we obtain $$A^\ast = \{ 0^{n_1} 1^{n_1} \cdots 0^{n_i} 1^{n_i} \mid i, n_1, \ldots, n_i \ge 0 \},$$ which is obviously not equal to $A$.

| cite | improve this answer | |
  • $\begingroup$ Yeah the * was in fact the Kleen star and I can easily disprove this with a counter example. $\endgroup$ – Ben Feb 4 '19 at 19:58

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.