# Can't understand a recursive definition of concatenation of two strings

I'm reading Rosen's Discrete Mathematics and its applications(6ed), but I can't understand a recursive definition about concatenation of two strings:

Two strings can be combined via the operation of concatenation. We can deﬁne the concatenation of the strings, denoted $\cdot$, recursively as follows. Basis step: If $w\in\Sigma^*$, then $w\cdot\lambda=w$ (where $\lambda$ is the empty string). Inductive step: If $w_1\in\Sigma^*$ and $w_2\in\Sigma^*$ and $x\in\Sigma$, then $w_1\cdot(w_2x)=(w_1\cdot w_2)x$.

I can't understand why there is an $x\in\Sigma$, and followed by an identity seems like an associative law. Isn't it just a definition about the concatenation of two strings??? Am I lost something???

This definition of concatenation is really just a more formal way of saying that in order to concatenate a string $w_1$ with a string $w_2$, we first append to $w_1$ the first character of $w_2$, then append to the result the second character of $w_2$, and continue in that fashion until we’ve exhausted $w_2$. For instance, it says that

\begin{align*} abc\cdot def&=(abc\cdot de)f\\ &=\big((abc\cdot d)e\big)f\\ &=\big((abcd\cdot\lambda)e\big)f\\ &=\big((abcd)e\big)f\\ &=(abcde)f\\ &=abcdef\;. \end{align*}

Note that it’s assumed that we know what it means to append a character to the end of a string; that’s what I did in the last two steps of the calculation.

I’ll prove by induction on the length of $w_2$ that the recursive definition really does tell you how to concatenate a string $w_1\in\Sigma^*$ with any string $w_2\in\Sigma^*$.

The basis step tells you how to concatenate a string $w_1$ with the string of length $0$, i.e., with the empty string: you just get $w_1$ back. Now suppose that you know how to concatenate $w_1$ with any string of length $n$; I claim that the induction step of the definition tells you how to concatenate $w_1$ with any string of length $n+1$. To see this, let $u$ be any string of length $n+1$. Then we can decompose $u$ into a string $w_2$ of length $n$ and a single character $x\in\Sigma$, so that $u=w_2x$. Then $$w_1\cdot w_2=w_1\cdot(w_2x)\;,$$ and the inductive step says that we can rewrite this as $$w_1\cdot w_2=w_1\cdot(w_2x)=(w_1\cdot w_2)x\;.$$ Since by hypothesis we already know how to concatenate $w_1$ with all strings of length $n$, we know how to form $w_1\cdot w_2$. It’s assumed from the beginning that we know what it means to append a single character to a string, so we also know what $(w_1\cdot w_2)x$ is, and therefore we know what $w_1\cdot u$ is. Finally, $u$ was an arbitrary string of length $n+1$, so we see that we now know how to concatenate $w_1$ with any string in $\Sigma^*$ of length $n+1$.

By induction, then, for each $n\in\Bbb N$ and each string $w_2\in\Sigma^*$ of length $n$ we know how to form $w_1\cdot w_2$. Finally, by definition every string in $\Sigma^*$ has length $n$ for some $n\in\Bbb N$, so we know how to form $w_1\cdot w_2$ for each $w_1\in\Sigma^*$.

• This is great but I would clarify that "we know how to" means "there is an algorithm which". So it is not any sort of recursive definition of concatenation itself (which is presumably already required for defining $\Sigma^*$), rather it is an inductive proof that concatenation is computable. Sep 3, 2013 at 5:21
• Yes! This is what the author means!! Now I understand totally!! Thanks soooooooooooooooo much~!!:P Sep 3, 2013 at 5:23
• @Dan: The definition given in the question is a recursive definition of concatenation, assuming that appending a character is a given. My answer is a proof in a more familiar form that the definition really does cover all cases. Sep 3, 2013 at 5:24
• @twoyoung: You’re very welcome! Sep 3, 2013 at 5:24
• Oh this is awesome... You save my afternoon. Mar 26, 2018 at 6:05

For those who find Rosen's treatment confusing, it may be preferable to shelve it and start from scratch with a more mathematical (i.e. set-theoretic) approach to strings and their concatenation based on the natural numbers $\Bbb N=\{0,1, ...\}$.

For $n\in\Bbb N$, define $[n]:=\{k\in\Bbb N:1\leqslant k\leqslant n\}$; so, in particular, $=\varnothing$ (the empty set). Given an arbitrary set $\varSigma$ (the "alphabet"), for $n\in \Bbb N$, a map $\sigma:[n]\to\varSigma:k\mapsto\sigma(k)$ is any set of ordered pairs $(k,x)$, with $k\in[n]$ and $x\in\varSigma$, such that $x'=x$ whenever $(k,x)\in\sigma$ and $(k,x')\in\sigma$, in which case we write $x=\sigma(k)$. A string in $\varSigma$ of length $n$ is just such a map. According to this definition, the empty string $\lambda$, of length $0$, is the empty map, namely $\varnothing$.

Given two strings in $\varSigma$, say $\sigma$ of length $m$ and $\tau$ of length $n$, their concatenation, denoted $\sigma\tau$, is defined as the map $$\sigma\tau:[m+n]\to\varSigma:k\mapsto(\sigma\tau)(k)=\begin{cases}\sigma(k) & \text{if }\qquad\quad 1\leqslant k\leqslant m,\\\tau(k-m) & \text{if }\quad m+1\leqslant k\leqslant m+n.\end{cases}$$Note that $\sigma\lambda=\lambda\sigma=\sigma$ follows immediately from the above definition, as either $m$ or $n$ is zero and one or other condition is obviated.

Notice that $x \in \Sigma$ but $w_1, w_2 \in \Sigma^*$ so it is not exactly the associative law. It is just saying that if you know how to perform the concatenation of a string and a single character then you can concatenate any two strings.

• A little clearer, but still somewhat confused. Thank you anyway:D Sep 3, 2013 at 2:48
• Would the concatenation "operator" be the same when operands are (string, string) and (string, character)? The notation seems a bit vague. Isn't the x the "recursive" part of the definition? Note that the basis step allows for w1 and w2 to be arbitrary strings, notably they do not need be the same length. Sep 3, 2013 at 2:52
• The text itself that you quoted isn't very clear, but I guess it is meant that concatenation is in some sense freely generated over the alphabet. Otherwise for example it's not clear how we know that $a \cdot b \ne a$ if $a, b \in \Sigma$ and $a \ne \lambda$ and $b \ne \lambda$. Sep 3, 2013 at 2:53
• Also, it seems really circular to use the superscript-star operator while defining concatenation. What is the definition of $\Sigma^*$ you are using? Sep 3, 2013 at 3:10
• I understand but it is still weird and seemingly inadequate to define a string in terms of an operation on strings and characters which itself is left undefined. I suppose there is some formal context I am missing but I think it would make more sense to just define a string of length $n$ as a function from $\{1 \dots n\}$ to $\Sigma$ or something like that and then define concatenation directly. Sep 3, 2013 at 7:12

Since @Brian M. Scott has said everything, I just provide a TL;DR version:

To append $w_1,w_2$, since $w_2$ can be formed by $\lambda x_1x_2x_3$, and from the basis step $w\lambda=w$: $$w_1\cdot(\lambda x_1x_2x_3)=(\dots(((w_1\cdot\lambda)x_1)x_2)\dots),$$

which is absolutely easy if we already know how to concatenate! (I'm reading the same Rosen's book too!)