例9.4设∑是字母的有穷集,称为字母表,∑中的有限个字母组成的序列称为∑上的串.对任何串w,串中字母的个数称作串的长度,记作|w|.长度是0的串称作空串,记作λ对任给的自然数k,令
显然∑
k
是∑上所有长度为k的串的集合.特别地有
其中∑
+
是∑上长度大于等于1的所有有限串的集合,而∑
*
是∑上所有有限串(包括空串)的集合.
运算.把串φ接在串w的后面,称之为连接运算.它是∑
*
上的二元运算.下面研究它的性质.
对任意w,φ,ψ∈∑
*
有
即连接运算满足结合律,但不满足交换律.它的幺元是空串λ.
在∑
*
上还可以定义一个一元运算 -  - 求一个串的反串,记作′.对任意w∈∑
*
,w=a
1
a
2
...a
n