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 define 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???
$\endgroup$4 Answers
$\begingroup$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^*$.
$\endgroup$ 5 $\begingroup$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, $[0]=\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.
$\endgroup$ $\begingroup$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.
$\endgroup$ 10 $\begingroup$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!)
$\endgroup$
