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
    What is $\Sigma$ for? What does the $*$-operation do?2012-09-12
  • 0
    Take an arbitrary word in $A*$ and show that it has an even number of zeroes. What else is there to prove?2012-09-12
  • 0
    What is ${}{}{}{}{}$ A*?2012-09-12
  • 2
    @Raskolnikov: It's the semigroup generated by $A$, I assume. $\Sigma$ is the alphabet.2012-09-12
  • 0
    Updated the questions with what A* is and what $\Sigma$ is.2012-09-12
  • 0
    Sure, if you have a group of people each of whom has an even number of jelly beans (not necessarily all the same), then the group has an even number of jelly beans.2012-09-12
  • 3
    Strictly speaking, in the usual terminology of formal language theory, $\Sigma$ is not a "language" but an _alphabet_ and $A$ and $A^*$ are _languages_ over that alphabet.2012-09-12
  • 0
    @HenningMakholm My mistake, thanks for the correction!2012-09-12
  • 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