PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (211)
Orphanage
Unclass'd (1)
Unproven (472)
Corrections (36)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
[parent] 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

\begin{displaymath} % latex2html id marker 409w \textrm{ is } \left\{ \begin{a... ...y }m\le n,\ \textrm{undefined otherwise.} \end{array}\right. \end{displaymath}
This $ n$ is necessarily unique, and is called the length of the word $ w$. The length of a word $ w$ is usually denoted by $ \vert w\vert$. 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 $ \vert\lambda\vert=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=\vert w\vert$. 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=\vert v\vert$ and $ n=\vert w\vert$. 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

\begin{displaymath} % latex2html id marker 461\circ(v,w)(i) = \left\{ \begin{a... ...{if }i\le m\ w(i-m) & \textrm{otherwise.} \end{array}\right. \end{displaymath}
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$, $ 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$.

Bibliography

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)

View style:

See Also: word

Other names:  juxtaposition
Also defines:  length, length of a word

This object's parent.

Attachments:
alternative treatment of concatenation (Definition) by rspuzio
Log in to rate this entry.
(view current ratings)

Cross-references: 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, words
There are 86 references to this entry.

This is version 12 of concatenation, born on 2007-06-18, modified 2007-11-11.
Object id is 9617, canonical name is Concatenation.
Accessed 1992 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
None.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)