| .字母表Σ和字符：字母表是字符的非空有穷集合，字符是字母表Σ中的一个元素。例如Σ=｛a，b｝，a或b是字符。
|
|
|
| .字符串：Σ中的字符组成的有穷序列。例如a，ab，aba，aaaa都是Σ的字符串。
|
|
|
| .字符串的长度：指字符串中的字符个数。如｜aba｜=3。
|
|
|
|
|
| .连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号“·”可省略。显然，对于字母表Σ的任意字符串S，S·ε=ε·S=S。
|
|
|
| .Σ*：是指包括空串ε在内的Σ上所有字符串的集合。例如，设Σ=｛a，b｝，Σ*=｛ε，a，b，aa，bb，ab，ba，aaa，…｝。
|
|
|
| .字符串的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为αn。α0=ε，αn=ααn-1=αn-1α（n>0）。
|
|
|
| .字符串集合的运算：设A，B代表字母表Σ上的两个字符串集合。
|
|
|
 或（合并）：A∪B=｛α｜α∈A或α∈B｝。
|
|
|
 积（连接）：AB=｛αβ｜α∈A且β∈B｝。
|
|
|
 幂：An=A·An-1=An-1：A（n>0），并规A0=｛ε｝。
|
|
|
 正则闭包＋：A+=A1∪A2∪A3∪…∪An∪…。
|
|
|
 闭包*：A*+A0∪A+。显然，Σ*=Σ0∪Σ1∪Σ2∪…∪Σn∪…。
|
|
|
