Q: Prove, using the definition of concatenation given in the text, that concatenation of strings is associative.
DEFINITION: The concatenation of strings $x$ and $y$, written $x \circ y$, or simply $xy$, is the string $x$ followed by the string $y$; formally, $w = x \circ y$ if and only if
$|w| = |x|+|y|$ and
$w(j) = x(j)$ for $j = 1,...,|x|$ and
$w(|x| + j) = y(j)$ for $j = 1,...,|y|$
This is an exercise from the book Elements of Theory of Computation. The following is my trying to give a proof.
We want to show that $(wx)y = w(xy)$.
Suppose $c = (wx)y$. Then by definition we have
- $|c| = |wx| + |y|$
- $c(j) = wx(j)$ for $j = 1,...,|wx|$
- $c(|wx| + j) = y(j)$ for $j = 1,...,|y|$
But again by definition
- $|wx| = |w| + |x|$
- $wx(j) = w(j)$ for $j=1,...,|w|$
- $wx(|w|+ j) = x(j)$ for $j = 1,...,|x|$
So we have
- $|c| = |w| + |x| + |y|$
- $c(j) = w(j)$ for $j = 1,...,|w|$
- $c(|w| + j) = wx(|w| + j) = x(j)$ for $j = 1,...,|x|$
- $c(|w| + |x| + j) = y(j)$ for $j = 1,...,|y|$
So I simply wrote the concetenation string in terms of the definition and left out the part for $w(xy)$ where the same work is involved to show that two resulting string is actually the same because they have the same length and also same symbols at the same indexes. I'd like to hear if anything is wrong with what I've done. I always feel like I lack something when doing proofs. So any comment would be helpful.
This theorem falls into the class of "so obvious that I'm surprised you're asked to do it". The string $abc$ is well-defined however we bracket it.
However, if you really want a proof, you could (with a heavy heart) do it by induction on the length of the final string. Let $a, b, c$ be strings. If $c$ is empty, then $(ab)c = ab$ and $a(bc) = a(b) = ab$. If $c$ has one element, then $(ab)c = abc = a(bc)$.
If $c$ has $n$ elements, then $(ab)c = (ab)(c_1 \dots c_n)$. Inductively since $c_n$ is a string of length $1$, we have $$\underbrace{(ab)}_{\alpha}(\underbrace{c_1 \dots c_{n-1}}_{\beta} \underbrace{c_n}_{\gamma}) = (\underbrace{ab}_{\alpha} (\underbrace{c_1 \dots c_{n-1}}_{\beta})) \underbrace{c_n}_{\gamma}$$
Inductively since $\beta$ is a string of length $n-1$, this is
$$(\underbrace{a}_{x} \underbrace{(b c_1 \dots c_{n-1})}_{y}) \underbrace{c_n}_{z}$$
Inductively since $c_n$ has length $1$, this is $$\underbrace{a}_{x} ((\underbrace{b c_1 \dots c_{n-1}}_{y}) \underbrace{c_n}_{z})$$
But $(b c_1 \dots c_{n-1}) c_n = b (c_1 \dots c_{n-1} c_n)$ inductively, so we obtain $$a (bc)$$