concatenation (original) (raw)

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 a⁢b. In order to define this rigorously, let us first do a little review of what words are.

Let Σ be a set whose elements we call letters (we also call Σ an alphabet). A (finite) word or a string on Σ is a partial function w:ℕ→Σ, (where ℕ is the set of natural numbers), such that, if dom⁡(w)≠∅, then there is an n∈ℕ such that

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 ∅, the empty set, is called the empty word, and is denoted by λ. It is easy to see that |λ|=0. Any element in the range of w has the form w⁢(i), but it is more commonly written wi. If a word w is not the empty word, then we may write it as w1⁢w2⁢⋯⁢wn, where n=|w|. The collection of all words on Σ is denoted Σ* (the asterisk * is commonly known as the Kleene star operation of a set). Using the definition above, we see that λ∈Σ*.

Now we define a binary operation ∘ on Σ*, called the concatenation on the alphabet Σ, as follows: let v,w∈Σ* with m=|v| and n=|w|. Then ∘(v,w) is the partial function whose domain is the set {1,…,m,m+1,…,m+n}, such that

The partial function ∘(v,w) is written v∘w, or simply v⁢w, when it does not cause any confusion. Therefore, if v=v1⁢⋯⁢vm and w=w1⁢⋯⁢wn, then v⁢w=v1⁢⋯⁢vm⁢w1⁢⋯⁢wn.

Below are some simple properties of ∘ on words:

• •
• •
  λ⁢w=w⁢λ=w.
• •
  As a result, Σ* together with ∘ is a monoid.
• •
  v⁢w=λ iff v=w=λ.
• •
  As a result, Σ* is never a group unless Σ*={λ}.
• •
  If a=b⁢c where a is a letter, then one of b,c is a, and the other the empty word λ.
• •
  If a⁢b=c⁢d where a,b,c,d are letters, then a=c and b=d.

Concatenation on Languages

The concatenation operation ∘ over an alphabet Σ can be extended to operations on languages over Σ. Suppose A,B are two languages over Σ, we define

When there is no confusion, we write A⁢B for A∘B.

Below are some simple properties of ∘ on languages:

• •
  (A⁢B)⁢C=A⁢(B⁢C); i.e. (http://planetmath.org/Ie), concatenation of sets of letters is associative.
• •
  Because of the associativity of ∘, we can inductively define An for any positive integer n, as A1=A, and An+1=An⁢A.
• •
  It is not hard to see that Σ*={λ}∪Σ∪Σ2∪⋯∪Σn∪⋯.

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. Prentice-Hall, Englewood Cliffs, New Jersey (1981).