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

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.