Concatenation on Words
Let be two words. Loosely speaking, the concatenation, or juxtaposition of and is the word of the form . 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 , (where is the set of natural numbers), such that, if , then there is an such that
This is necessarily unique, and is called the length of the word . The length of a word is usually denoted by . The word whose domain is , the empty set, is called the empty word, and is denoted by . It is easy to see that . Any element in the range of has the form , but it is more commonly written . If a word is not the empty word, then we may write it as , where . 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 with and . Then is the partial function whose domain is the set , such that
The partial function is written , or simply , when it does not cause any confusion. Therefore, if and , then .
Below are some simple properties of on words:
is associative: .
As a result, together with is a monoid.
As a result, is never a group unless .
If where is a letter, then one of is , and the other the empty word .
If where are letters, then and .
Concatenation on Languages
The concatenation operation over an alphabet can be extended to operations on languages over . Suppose are two languages over , we define
When there is no confusion, we write for .
Below are some simple properties of on languages:
; i.e. (http://planetmath.org/Ie), concatenation of sets of letters is associative.
Because of the associativity of , we can inductively define for any positive integer , as , and .
It is not hard to see that .
- 1 H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
|Date of creation||2013-03-22 17:16:38|
|Last modified on||2013-03-22 17:16:38|
|Last modified by||CWoo (3771)|
|Defines||length of a word|