concatenation
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.
-
•
iff .
-
•
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 .
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).
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 |