concatenation


Concatenation on Words

Let a,b be two words. Loosely speaking, the concatenationMathworldPlanetmath, 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 Σ be a set whose elements we call letters (we also call Σ an alphabet). A (finite) word or a string on Σ is a partial functionMathworldPlanetmath w:Σ, (where is the set of natural numbers), such that, if dom(w), then there is an n such that

w is {defined for every mn,undefined otherwise.

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 setMathworldPlanetmath, is called the empty wordPlanetmathPlanetmathPlanetmath, 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 w1w2wn, where n=|w|. The collectionMathworldPlanetmath of all words on Σ is denoted Σ* (the asterisk * is commonly known as the Kleene star operationMathworldPlanetmath of a set). Using the definition above, we see that λΣ*.

Now we define a binary operationMathworldPlanetmath 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

(v,w)(i)={v(i)if imw(i-m)otherwise.

The partial function (v,w) is written vw, or simply vw, when it does not cause any confusion. Therefore, if v=v1vm and w=w1wn, then vw=v1vmw1wn.

Below are some simple properties of on words:

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

  • λw=wλ=w.

  • As a result, Σ* together with is a monoid.

  • vw=λ iff v=w=λ.

  • As a result, Σ* is never a group unless Σ*={λ}.

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

  • If ab=cd 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 languagesPlanetmathPlanetmath over Σ. Suppose A,B are two languages over Σ, we define

AB:={uvuA,vB}.

When there is no confusion, we write AB for AB.

Below are some simple properties of on languages:

  • (AB)C=A(BC); 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=AnA.

  • It is not hard to see that Σ*={λ}ΣΣ2Σn.

Remark. A formal languageMathworldPlanetmath containing the empty word, and is closed under concatenation is said to be monoidal, since it has the structureMathworldPlanetmath of a monoid.

References

  • 1 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
Title concatenation
Canonical name Concatenation
Date of creation 2013-03-22 17:16:38
Last modified on 2013-03-22 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