How to prove $L \cdot L^{*} = L^{+}$

How can one formally prove

$L \cdot L^{*} = L^{+}$

It looks obvious to me since with the concatenation you get rid of $\varepsilon$, but I cannot think of a formal proof through induction or something.

-
? this is by definition –  vzn Oct 30 '12 at 18:26
Or if not by definition, a small step away from the definitions. –  Dave Clarke Oct 30 '12 at 18:55
Well, I would say $L \cdot L^{*} = L \cdot \bigcup_{i \ge 0} L^{i} = \bigcup_{i \ge 1}L^{i} = L^{+}$ However, this is an old exercise I found and the task is to use induction, which seems not necessary to me. –  user1658887 Oct 30 '12 at 19:03
@user1658887 Your proof looks good enough for me. Perhaps they wanted you to use induction on $i$, though this seems pointless since you won't be using the induction hypothesis. –  Yuval Filmus Oct 30 '12 at 20:09
I don't see how induction can be used here. You can't get from $\bigcup_{i=0}^n$ to $\bigcup_{i=0}^\infty$ by induction. –  Raphael Oct 31 '12 at 9:51

1 Answer

To summarize the comments.

A. Sometimes $L^+$ is defined to be $L\circ L^*$, where '$\circ$' is the concatenations operator.

B. Assume the following definitions,

$L^* \equiv \{\varepsilon\} \cup L \cup L^2 \cup \cdots$

$L^+\equiv L \cup L^2 \cup \cdots$

Then, by the properties of the concatenation operator, $L\circ L^i = L^{i+1}$. Explicitly for the case of $i=0$, it also holds that $L\circ\{\epsilon\} = L$.

Then, \begin{align} L\circ L^* &= L \circ \left( \{\varepsilon\} \cup L \cup L^2 \cup \cdots \right ) \\ &= (L\circ \{\varepsilon\}) \cup (L\circ L) \cup (L \circ L^2) \cup \cdots \\ &= L \cup L^2 \cup \cdots \\ &\equiv L^+ \end{align}

The only missing part is to explain the second transition--The distributivity of the concatenation operator over unions.

-
Thx. Just to make sure: You would also say that induction does not make any sense in this case? –  user1658887 Oct 31 '12 at 7:56
As Raphael wrote above, induction is problematic when talking about $n=\infty$, although it can be used to prove for any arbitrary large (but finite) $n$. –  Ran G. Nov 1 '12 at 0:51