3
$\begingroup$

In class, my professor proposed the following:

Let $A = \{w \mid w \text{ contains an even number of $0$'s} \}$ where $\Sigma=\{0,1\}$ is the alphabet.

And then asked the class whether $A^* = A$, where $A^*$ is the Kleene star operation of A.

Intuitively, I feel that $A^* = A$ since $A^*$ will always have some multiple of even $0$'s, which means that it still has an even amount of zeros, but I don't know how to prove it rigorously.

Note: In class, we decided that the empty string $\varepsilon$ had an even number of zeros, and thus belonged to both sets. (This is not homework, just a question my professor proposed in class and left open for next lecture)

  • 0
    The sum of a collection of even numbers is even, hence $A^* \subset A$.2012-09-12

1 Answers 1

4

Your intuition is correct.

To prove it correct, the most straightforward aproach is to show the two inclusions $A\subseteq A^*$ and $A^*\subseteq A$. The first one of these is trivially true for every $A$. For the second one, suppose $w$ is a member of $A^*$; our task is then to show that $w\in A$. By definition of $A^*$, $w$ is the concatenation of zero or more words from $A$. Therefore the total number of zeroes in $w$ is the sum of zero or more even numbers, and therefore ...

  • 1
    Thanks, the major step I was missing was " A⊆A* and A*⊆A".2012-09-18