2
$\begingroup$

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!

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

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) $$

which is a contradiction.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Charmaine N Ndolo Oct 29 '17 at 19:45
1
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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 })$$

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

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.