|
|
|
|
![[parent]](http://images.planetmath.org:8080/images/uparrow.png)
concatenation
|
(Definition)
|
|
|
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 $\Sigma$ be a set whose elements we call letters (we also call $\Sigma$ an alphabet). A (finite) word or a string on $\Sigma$ is a partial function $w:\mathbb{N} \to \Sigma$ , (where $\mathbb{N}$ is the set of natural numbers), such
that, if $\operatorname{dom}(w)\ne \varnothing$ , then there is an $n\in \mathbb{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 $\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_1w_2\cdots w_n$ , where $n=|w|$ . The collection of all words on $\Sigma$ is denoted $\Sigma^*$ (the asterisk $^*$ is commonly known as the Kleene star operation of a set). Using the definition above, we see that $\lambda\in \Sigma^*$ .
Now we define a binary operation $\circ$ on $\Sigma^*$ , called the concatenation on the alphabet $\Sigma$ , as follows: let $v,w\in \Sigma^*$ with $m=|v|$ and $n=|w|$ . Then $\circ(v,w)$ is the partial function whose domain is the set $\lbrace 1, \ldots, m, m+1, \ldots, m+n\rbrace$ , 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\cdots v_m$ and $w=w_1\cdots w_n$ , then $vw=v_1\cdots v_mw_1\cdots w_n$ .
Below are some simple properties of concatenation $\circ$ .
- $\circ$ is associative: $(uv)w=u(vw)$ .
- $\lambda w=w\lambda = w$ .
- As a result, $\Sigma^*$ together with $\circ$ is a monoid.
- $vw=\lambda$ iff $v=w=\lambda$ .
- As a result, $\Sigma^*$ is never a group unless $\Sigma^*=\lbrace \lambda\rbrace$ .
- 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$ .
Given two alphabets $A,B$ , let $\Sigma=A\cup B$ . Let $\circ$ be the concatenation on $\Sigma$ . We can define $A\circ B=\lbrace a\circ b \in \Sigma^* \mid a\in A\mbox{, }b\in B\rbrace$ . This is the concatenation of $A$ and $B$ . When there is no confusion, we write $AB$ for $A\circ B$ .
Below are some simple properties of concatenation of sets of letters:
- $(AB)C=A(BC)$ ; i.e., 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^nA$ .
- It is not hard to see that $\Sigma^*=\lbrace \lambda \rbrace \cup \Sigma \cup \Sigma^2 \cup \cdots \cup \Sigma^n \cup \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.
- 1
- H.R. Lewis, C.H. Papadimitriou Elements of the Theory of Computation. Prentice-Hall, Englewood Cliffs, New Jersey (1981).
|
"concatenation" is owned by CWoo. [ full author list (2) ]
|
|
(view preamble | get metadata)
See Also: word
| Other names: |
juxtaposition, monoidal |
| Also defines: |
length, length of a word, monoidal language |
This object's parent.
|
|
Cross-references: structure, closed under, formal language, integer, positive, group, iff, monoid, associative, properties, binary operation, operation, Kleene star, collection, range, easy to see, empty word, empty set, domain, natural numbers, partial function, string, finite, alphabet, elements, words
There are 138 references to this entry.
This is version 13 of concatenation, born on 2007-06-18, modified 2009-05-15.
Object id is 9617, canonical name is Concatenation.
Accessed 5922 times total.
Classification:
| AMS MSC: | 68Q70 (Computer science :: Theory of computing :: Algebraic theory of languages and automata) | | | 20M35 (Group theory and generalizations :: Semigroups :: Semigroups in automata theory, linguistics, etc.) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
