concatenation
Concatenation on Words
Let $a,b$ be two words. Loosely speaking, the concatenation^{}, or juxtaposition of $a$ and $b$ is the word of the form $ab$. In order to define this rigorously, let us first do a little review of what words are.
Let $\mathrm{\Sigma}$ be a set whose elements we call letters (we also call $\mathrm{\Sigma}$ an alphabet). A (finite) word or a string on $\mathrm{\Sigma}$ is a partial function^{} $w:\mathbb{N}\to \mathrm{\Sigma}$, (where $\mathbb{N}$ is the set of natural numbers), such that, if $\mathrm{dom}(w)\ne \mathrm{\varnothing}$, then there is an $n\in \mathbb{N}$ such that
$$w\text{is}\{\begin{array}{cc}\text{defined for every}m\le n,\hfill & \\ \text{undefined otherwise.}\hfill & \end{array}$$ 
This $n$ is necessarily unique, and is called the length of the word $w$. The length of a word $w$ is usually denoted by $w$. The word whose domain is $\mathrm{\varnothing}$, the empty set^{}, is called the empty word^{}, and is denoted by $\lambda $. It is easy to see that $\lambda =0$. Any element in the range of $w$ has the form $w(i)$, but it is more commonly written ${w}_{i}$. If a word $w$ is not the empty word, then we may write it as ${w}_{1}{w}_{2}\mathrm{\cdots}{w}_{n}$, where $n=w$. The collection^{} of all words on $\mathrm{\Sigma}$ is denoted ${\mathrm{\Sigma}}^{*}$ (the asterisk ${}^{*}$ is commonly known as the Kleene star operation^{} of a set). Using the definition above, we see that $\lambda \in {\mathrm{\Sigma}}^{*}$.
Now we define a binary operation^{} $\circ $ on ${\mathrm{\Sigma}}^{*}$, called the concatenation on the alphabet $\mathrm{\Sigma}$, as follows: let $v,w\in {\mathrm{\Sigma}}^{*}$ with $m=v$ and $n=w$. Then $\circ (v,w)$ is the partial function whose domain is the set $\{1,\mathrm{\dots},m,m+1,\mathrm{\dots},m+n\}$, such that
$$\circ (v,w)(i)=\{\begin{array}{cc}v(i)\hfill & \text{if}i\le m\hfill \\ w(im)\hfill & \text{otherwise.}\hfill \end{array}$$ 
The partial function $\circ (v,w)$ is written $v\circ w$, or simply $vw$, when it does not cause any confusion. Therefore, if $v={v}_{1}\mathrm{\cdots}{v}_{m}$ and $w={w}_{1}\mathrm{\cdots}{w}_{n}$, then $vw={v}_{1}\mathrm{\cdots}{v}_{m}{w}_{1}\mathrm{\cdots}{w}_{n}$.
Below are some simple properties of $\circ $ on words:

•
$\circ $ is associative: $(uv)w=u(vw)$.

•
$\lambda w=w\lambda =w$.

•
As a result, ${\mathrm{\Sigma}}^{*}$ together with $\circ $ is a monoid.

•
$vw=\lambda $ iff $v=w=\lambda $.

•
As a result, ${\mathrm{\Sigma}}^{*}$ is never a group unless ${\mathrm{\Sigma}}^{*}=\{\lambda \}$.

•
If $a=bc$ where $a$ is a letter, then one of $b,c$ is $a$, and the other the empty word $\lambda $.

•
If $ab=cd$ where $a,b,c,d$ are letters, then $a=c$ and $b=d$.
Concatenation on Languages
The concatenation operation $\circ $ over an alphabet $\mathrm{\Sigma}$ can be extended to operations on languages^{} over $\mathrm{\Sigma}$. Suppose $A,B$ are two languages over $\mathrm{\Sigma}$, we define
$$A\circ B:=\{u\circ v\mid u\in A,v\in B\}.$$ 
When there is no confusion, we write $AB$ for $A\circ B$.
Below are some simple properties of $\circ $ on languages:

•
$(AB)C=A(BC)$; i.e. (http://planetmath.org/Ie), concatenation of sets of letters is associative.

•
Because of the associativity of $\circ $, we can inductively define ${A}^{n}$ for any positive integer $n$, as ${A}^{1}=A$, and ${A}^{n+1}={A}^{n}A$.

•
It is not hard to see that ${\mathrm{\Sigma}}^{*}=\{\lambda \}\cup \mathrm{\Sigma}\cup {\mathrm{\Sigma}}^{2}\cup \mathrm{\cdots}\cup {\mathrm{\Sigma}}^{n}\cup \mathrm{\cdots}$.
Remark. A formal language^{} containing the empty word, and is closed under concatenation is said to be monoidal, since it has the structure^{} of a monoid.
References
 1 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. PrenticeHall, Englewood Cliffs, New Jersey (1981).
Title  concatenation 
Canonical name  Concatenation 
Date of creation  20130322 17:16:38 
Last modified on  20130322 17:16:38 
Owner  CWoo (3771) 
Last modified by  CWoo (3771) 
Numerical id  17 
Author  CWoo (3771) 
Entry type  Definition 
Classification  msc 20M35 
Classification  msc 68Q70 
Synonym  juxtaposition 
Synonym  monoidal 
Related topic  Word 
Defines  length 
Defines  length of a word 
Defines  monoidal language 