I am to prove that being $x$ a string and $|x|$ its length, one should have the following property hold true for any two strings $x$ and $y$:

$$ |xy| = |x| + |y| $$

with $x, y \in \Sigma^*$.

To prove this, I am expected to make use of the following two definitions:

  1. for $x=\epsilon$ we have $|x|=0$
  2. for $x=au$, being $u \in \Sigma^*$ and $a \in \Sigma$ we have $|x|=1+|u|$

Intuitively it is easy to understand what is being asked here. The idea is to prove that the length of the concatenation of any two strings is equal to the sum of their individual lenghts.

What I am failing to realise is how to tackle the problem. Should I make use of induction? Just algebraic manipulation?

Any pointers would be welcome.

  • 2
    $\begingroup$ Induction over $|x|$ seems indicated. $\endgroup$ – Did Feb 20 '11 at 18:19
  • $\begingroup$ Induction should work. For instance, use induction on $|y|$. $\endgroup$ – Myself Feb 20 '11 at 18:20
  • $\begingroup$ Thanks guys, I think I did it. I will now post an answer on this. $\endgroup$ – devoured elysium Feb 20 '11 at 18:44
  • $\begingroup$ If this is a homework assignment, please say so. Could this be solved by observing that string concatenation is a monoid with $\epsilon$ as the identity and $|\cdot|$ mapping to integers with $+$ as operation and $0$ as identity? $\endgroup$ – Christian Lindig Feb 20 '11 at 18:44
  • $\begingroup$ Well, I am studying this in my spare time and found some exercises on this on the net. So I guess yes, they are homework. And no, I do not gain anything by having someone do it for me. I know nothing about monoids. $\endgroup$ – devoured elysium Feb 20 '11 at 19:04

See this answer and this one for general advice and discussion on induction. Your argument above is, alas, neither very clear nor correct.

So, we have that $|\epsilon|=0$, and that if $x=au$ with $a\in\Sigma$, $u\in\Sigma^*$, then $|x|=1+|u|$. We want to prove that for all $x,y\in\Sigma^*$, we have $|xy|=|x|+|y|$.

What you really need here is an explicit definition of $\Sigma^*$, because you need to be able to handle elements of $\Sigma^*$. I'm guessing, pending you posting the definition, that you have a certain "alphabet" $\Sigma$, and then define $\Sigma^*$ as the collection of all strings of letters from $\Sigma$ in some way.

Assuming the intended definition is the definition in this page, we can proceed as follows.

For all $n$, if $y\in \Sigma^*$ and $x\in\Sigma^n$, then $|xy|=|x|+|y|$.

If we can prove this, it will follow that for all $x$ in $\cup\Sigma^n = \Sigma^*$, we have $|xy|=|x|+|y|$, which is what we want to prove.

We will prove the proposition above by induction on $n$.

Base. $n=0$. Let $x\in\Sigma^0$. Then $x=\epsilon$, so $xy = y$ and $|x|=0$ by definition of $|\epsilon|$. Therefore, $|xy|=|y|=0+|y| = |x|+|y|$, so the equality holds.

Inductive step. We want to prove that if it is true that for all $z\in \Sigma^k$, $|zy|=|z|+|y|$, then it is true that for all $x\in\Sigma^{k+1}$, we also have $|xy|=|x|+|y|$.

Induction hypothesis. If $z\in\Sigma^k$, then $|zy|=|z|+|y|$.

Let $x\in\Sigma^{k+1}$. We want to prove that $|xy|=|x|+|y|$.

Since $x\in\Sigma^{k+1}$, then $x=au$ with $a\in\Sigma$ and $u\in\Sigma^k$.

Then we have by the definition of $|\cdot|$ that $$|xy| = |(au)y| = |a(uy)| = 1 + |uy|.$$ And by the Induction Hypothesis, since $|u|\in\Sigma^k$, we get $$|xy| = 1+|uy| = 1+(|u|+|y|) = (1+|u|)+|y|.$$ But by the definition of $|\cdot|$ we have $|x| = |au| = 1+|u|$, so $$|xy| = (1+|u|)+|y| = |x|+|y|,$$ as desired.

Thus, if for every $z\in\Sigma^k$ we have $|zy|=|z|+|y|$, then for every $x\in\Sigma^{k+1}$ we have $|xy|=|x|+|y|$.

By induction, we conclude that for all $n$, if $x\in\Sigma^n$ then $|xy|=|x|+|y|$.

Therefore, we have that for all $x\in\mathop{\cup}\limits_{n=0}^{\infty}\Sigma^n$, $|xy| = |x|+|y|$.

Thus, for all $x\in \Sigma^*$, $|xy|=|x|+|y|$.

Since $y\in\Sigma^*$ is arbitrary, we conclude that

For all $x,y\in \Sigma^*$, $|xy|= |x|+|y|$

as claimed. QED

  • $\begingroup$ @Arturo If I understand your post correctly, the first two thirds are off topic. Simply put, there is no problem at all with the definitions of $\Sigma^*$ and of $|x|$ for $x$ in $\Sigma^*$. This is basic stuff of the field, see en.wikipedia.org/wiki/String_%28computer_science%29 for example (so I would not blame the OP for such an omission). In fact, one can forget all this top-down and bottom-up stuff (and I am not sure you really meant to write bottoms-up here...) and your recursive definition of $\Sigma^*$. .../... $\endgroup$ – Did Mar 26 '11 at 23:57
  • $\begingroup$ .../... Instead, why not use the classical Cartesian products $\Sigma^n$ for every positive integer $n$ (and not your sets $\Sigma_n$), as everybody else does? This would simplify the only relevant part of your post (the last third, where you perform the proof by induction that I hinted at one month ago, following exactly the way I explained then), where your $\Sigma_n$ sets only complicate things. $\endgroup$ – Did Mar 26 '11 at 23:57
  • $\begingroup$ @Didier: I don't know what definition of $\Sigma^*$ the OP has, or what properties he knows. If the definition is via the bottoms up approach and this is standard and assumed,, then yes, you can drop the entire first part and jump until the last part. The $\Sigma_n$ I defined are simply equal to $\cup_{i=1}^n\Sigma^n$ as per the definition in the Wikipedia page, though, so I don't see how they "complicate things"... $\endgroup$ – Arturo Magidin Mar 27 '11 at 0:14
  • $\begingroup$ @Arturo The so called Kleene closure $\Sigma^*$ of $\Sigma$ is by definition the union of the $\Sigma^n$, each Cartesian product $\Sigma^n$ is by definition the set of functions from $\{1,2,...,n\}$ to $\Sigma$. You still need to know how to compose a function from $\{1,2,...,n\}$ to $\Sigma$ with a function from $\{1,2,...,k\}$ to $\Sigma$, to produce a function from $\{1,2,...,n+k\}$ to $\Sigma$ (a not too difficult task), et voilà! No recursion. No bottom-up approach. Sorry to insist, but this is really basic stuff and yes, everybody defines $\Sigma^*$ in this way. $\endgroup$ – Did Mar 27 '11 at 0:33
  • $\begingroup$ @Didier: Yes, I know this is basic and easy. I could do it in my sleep and with one hand tied behind my back. And behind everything you say, there is an application of the recursion theorem which perhaps you aren't seeing. And yet, it's there. $\endgroup$ – Arturo Magidin Mar 27 '11 at 1:26

So, I will only cover here how to solve this for the inductive step, as the other is rather easy (not that the inductive step one isn't!).

Considering a string $x'=\lambda x$ we have

$$\begin{align} |x'y| &= |x'|+|y| \\ |\lambda xy| &= |\lambda x| + |y| \\ |\lambda z| &= 1 + |x| + |y| \\ 1 + |z| &= 1 + |x| + |y| \\ 1+|xy| &= 1 + |xy| \end{align}$$

  • 3
    $\begingroup$ Sorry to be blunt but this is not a proof. Not nearly. A proof by induction begins with stating precisely an induction hypothesis $H_n$. Then one proves that $H_1$ holds (for instance). Then one proves that, for every $n\ge1$, if $H_n$ holds, then $H_{n+1}$ holds. If you do all this, you won in the sense that you proved that $H_n$ holds for every $n\ge1$. $\endgroup$ – Did Feb 20 '11 at 19:50
  • 1
    $\begingroup$ as stated above, this is the inductive step (Hn+1). $\endgroup$ – devoured elysium Feb 20 '11 at 21:31
  • $\begingroup$ The inductive step is not to prove that $H_n$ holds nor to prove that $H_{n+1}$ holds. The inductive step is to prove that if $H_n$ holds then $H_{n+1}$ holds. For example, consider for $H_n$ the assertion that the sum of the powers of $2$ from $2^0=1$ to $2^n$ is $2^{n+1}+7$. Then, for every nonegative $n$, $H_n$ does imply $H_{n+1}$ even though every $H_n$ is false. $\endgroup$ – Did Feb 20 '11 at 22:24
  • 1
    $\begingroup$ If you want, you can show us noobs how to do it right as a separate answer (and have the 15 points, as although several people helped me understand the problem, they only did it as comments!). $\endgroup$ – devoured elysium Feb 22 '11 at 22:39
  • 4
    $\begingroup$ OK (but next time you could spare us this us noobs thing). As I said, A proof by induction begins with stating precisely an induction hypothesis $H_n$, so what is your $H_n$? Hint: the answer is in my first comment to your post. $\endgroup$ – Did Feb 23 '11 at 9:05

I have upvoted Arturo Magidin's answer. But aren't we shooting with cannons on sparrows here? A fundamental principle of counting is that it is additive on disjoint sets. Now count the number of cells that are occupied by your strings.


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.