Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

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.

share|improve this question
? this is by definition – vzn Oct 30 '12 at 18:26
2  
Or if not by definition, a small step away from the definitions. – Dave Clarke Oct 30 '12 at 18:55
2  
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
1  
@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
2  
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
show 1 more comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.