# When is the empty word part of $A^+$?

My professor mentioned the below statement in class but without a proof. I am trying to prove it for myself as I don't understand 100% why this is always the case. Given is A, a subset of {0,1}$^*$.

ε $\in\ A^+$ <-> ε $\in\ A$, where ε is the empty word. I thought of doing a proof by contradiction to show -> by assuming the empty word is not part of A$^+$.

Any help is much appreciated!

• Try showing either implication on its own. Be aware that you can show the contraposition instead, if that's more convenient. – Raphael Oct 29 '17 at 20:26
• I've tried showing the -> using length, but I'm stuck when it comes to <- – Charmaine N Ndolo Oct 29 '17 at 20:27

You can look at the length of words.

Any element of $A^+$ is a concatenation

$$a_1 a_2 \ldots a_n$$

where $a_i \in A$ and $n \geq 1$. The length of such a word is

$$L(a_1 a_2 \ldots a_n) = L(a_1) + L(a_2) + \ldots + L(a_n)$$

But the length is always nonnegative; for example,

$$0 \leq L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n)$$

If you're given that

$$\epsilon = a_1 a_2 \ldots a_n$$

then putting all of the above together gives

$$0 \leq L(a_1) \leq L(\epsilon) = 0$$

and thus $L(a_1) = 0$, so $a_1 = \epsilon$ and $\epsilon \in A$.

If you were to assume that $\epsilon \notin A$, you could modify the above argument by the fact that $L(a_i)$ must be positive, and so

$$0 < L(a_1) \leq L(a_1) + L(a_2) + \ldots + L(a_n)$$

and then the final deduction would be

$$0 < L(\epsilon)$$

• Thanks @Hurkyl. That makes a lot of sense, I didn't think of using the length as an argument. What about proving the other direction? – Charmaine N Ndolo Oct 29 '17 at 19:45

For any languages $K,L$ the shortest string in $K(L\cup\varepsilon)$ is the shortest string in $K$.

Now $A^+ = A(A^+\cup\varepsilon)$. Hence the shortest string in $A^+$ is the shortest string in $A$.

This trivially follows from the definition of the Kleene plus operation. $A^+$ is known as the Kleene plus operation on the set $A$. This operation omits the $A^0=\{\epsilon\}$ in the the Kleene star operation on the set $A$. So, $\epsilon \in A^+ = A \cup A^2 \cup A^3\dots$ if and only if $\epsilon \in A$.

Proof of $\epsilon \in A^+ \Rightarrow \epsilon \in A$.
Let $\epsilon \in A^+$. Then $\epsilon \in A \cup A^2 \cup A^3\dots$. This means $\epsilon \in A^i$ for some $i>0$. But $\epsilon \in A^i$ if $\epsilon \in A A\dots A$ ($i$ times) if $\epsilon \in A$.

Proof of $\epsilon \in A \Rightarrow \epsilon \in A^+$.
Since $A^+ = A \cup A^2 \cup A^3\dots$ and $\epsilon \in A$, we have $\epsilon \in A^+$.

If $A$ and $B$ are sets of strings then $AB$ is defined as a set $$\{uv \mid u \in A, v\in B\}$$ and $$A^n = A A \dots A \ \ \ (n \text{ times })$$

• I feel like your last sentence just rephrases my question. What is the proof here exactly? – Charmaine N Ndolo Oct 29 '17 at 20:29