定义2 如果z=是一个符号串,则是z和头,而/是z的尾。如果 是非空的,那么γ是固有尾:同样如果/非空,那么x是固有头 例:设z=abC,那么的头是a,ab,abc除abC外,其它都 是固有头。Z的尾是EC,bC,abC:z的固有尾是EC,bC
定义 2.6 如果z=xy是一个符号串，则x是z和头，而y是z的尾。如果x 是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。 例：设z=abc，那么z的头是ε,a，ab，abc。除abc外，其它都 是固有头。z的尾是ε,c，bc，abc。z的固有尾是ε,c，bc
定义2.7 x、y是同一字母表上的两个符号串,把y的符号写在的 符号之后得到的符号串,称为的连接。记为y 例:=ab,y=Wabu贝 z=Xy=abywabu 显然:X1+y=|2 EX-XE=X
定义 2.7 设x、y 是同一字母表上的两个符号串，把y的符号写在X的 符号之后得到的符号串，称为的连接。记为xy 例：x=ab，y=wabu 则 z=xy=abywabu 显然：|x|+|y|=|z| εx=xε=x
定义2.8 设x是符号串,把自身连接门次得到符号串乙,即z=x…x(n 个x),称为符号串x的方幂,记为z=xn 例:×=8×=X×2=X××3=X 定义2.9 符号串集合若集合A中的一切元素都是其字母表上的符号 串,则称A为该字母表上的符号串集合。 注意:E、(B和(表示空集)的区别
定义 2.8 设x是符号串，把x自身连接n次得到符号串z,即z=xx···xx(n 个x)，称为符号串x的方幂,记为z=xn 例：x 0=ε x1=x x2=xx x3=xxx ··· 定义 2.9 符号串集合若集合A中的一切元素都是其字母表上的符号 串，则称A为该字母表上的符号串集合。 注意：ε、{ε}和Φ（表示空集）的区别
定义210 两个符号串集合A和B的乘积AB定义为: AB={xyx∈A且y∈B 例:设A={abC},B={b,cda则集合 AB=ab, ac ada, bcb, bcc, bcda j 注意:由于Ex=xE=x因此!E}A=At}=A,但A=A0=0 则: A={E} Al-A A2=AA An=An-IA=AAn-1(n>0)
定义 2.10 两个符号串集合A和B的乘积AB定义为： AB={xy|x∈A且y∈B} 例：设A={a,bc}，B=｛b,c,da｝则集合 AB={ab,ac,ada,bcb,bcc,bcda｝。 注意：由于εx=xε=x 因此{ε}A=A{ε}=A ，但ΦA=AΦ=Φ 则： A 0={ε} A 1=A A 2=AA A n=An-1A=AAn-1（n>0）
显然: ∑1是字母表中的所有单个字符组成的字符串 2是所有由字母表中二个的字符组成的字符串 是所有由字母表中长度为的子考符串 ∑是所有由字母表中三个的字符组成的字 定义2.11 A的闭包A*=A0UAUA2U A的正闭包A+≡AUA2UA3U 显然A≡AA*≡AAA半=A0UA+
显然： Σ 1是字母表中的所有单个字符组成的字符串 Σ 2是所有由字母表中二个的字符组成的字符串 Σ 3是所有由字母表中三个的字符组成的字符串 Σ n是所有由字母表中长度为n的字符串集合 定义 2.11 A的闭包 A*=A0∪A 1∪A 2∪··· A的正闭包 A += A1∪A 2∪A 3∪··· 显然A +=AA*=A*A A*=A0∪A +