22文法和语言的定义 2.21基本概念和术语 符号表(呲符号集)由若干符号组成的有限 空集合。如{a,b,c,S,T,,+,;y,8,} 2。符号电用符号表中的符号所组成的任何有限 序列。 符号的长度=符号串中所含符号的个数 例:mbm的长度为3。记为:|aba|=3 空不含任何符号的符号串,记为ε。显然, E|=0 6
6 2.2 文法和语言的定义 2.2.1 基本概念和术语 1。符号表（或符号集） 由若干符号组成的有限 非空集合。如{a,b,c,S,T,*,+,;,.,8,$} 2。符号串 用符号表中的符号所组成的任何有限 序列。 符号串的长度 = 符号串中所含符号的个数 例：aba的长度为3。记为：|aba|=3 空串 不含任何符号的符号串，记为 。显然，| |= 0
2.2,基祝念和术语(续) 3。符号串的前(后)缀及子申 设8x是符号串,若=以则aB和6都是的子串 当α=ε时,称β是x的前缀。当δ=ε时,称β是x的后缀。 x的任何前缀或后缀都是x的子串,反之不成立 E和x本身既是x的前缀和后缀,也是x的子串 4。符号串的连接和方幂 连接设xy是符号串,将y直接地拼接到x之后 所得的新符号串称为x与y的连接,记为xy 7
7 2.2.1 基本概念和术语（续） 3。符号串的前（后）缀及子串 设,,,x是符号串，若x= ,则,和 都是x的子串； 当= 时，称 是x的前缀。 当= 时，称 是x的后缀。 x的任何前缀或后缀都是x的子串，反之不成立。 和x本身既是x的前缀和后缀，也是x的子串。 4。符号串的连接和方幂 连接 设x,y是符号串，将y直接地拼接到x之后 所得的新符号串称为x与y的连接，记为xy
2.2,基祝念和术语(续) 注意,一般说来,q不等x;但 =8x 方幂符号串x与其自身的n-次连接称为x的 n次方幂,记为 x即 n-1 xX 这里,我们约定:x0=E ,8
8 2.2.1 基本概念和术语（续） 注意，一般说来，xy不等于yx；但 x=x=x 方幂 符号串x与其自身的n-1次连接称为 x 的 n 次方幂，记为 = = = = − 0 1 1 , : 2,3,...... x x x x x x n x n n n 这里 我们约定 即
2.2,基祝念和术语(续) 5。符号串集合的和与积 设A,B为两个符号串集合,定义 和A+B(或4UB)={w|w∈A,或和∈B 积AB(或AB)={xy∈A,y∈B A+=+A=A;A=A=;{}A=A{e}=A 6。符号串集的方幂与闭包 设A是符号串的集合,定义A的方幂 A(n>0) oo A的正闭包:A+=UA2=A+A2+ 字A的自反传递闭包:A=A++{}
9 2.2.1 基本概念和术语（续） 5。符号串集合的和与积 设A，B为两个符号串集合，定义 和 A+B（或A B） ={w | w A，或 w B} 积 A•B（或 AB）= { xy |x A, y B} A+ = +A = A ； A = A = ；{}A = A{} = A 6。符号串集的方幂与闭包 : { } : { } ( 0) , : * 2 1 0 1 = + = = + + = = + = + − A A A A A A A A A A A A n A A i i n n 的自反传递闭包 的正闭包 设 是符号串的集合 定义 的方幂