串和语言(2) 和串有关的术语（以banana为例） 前缀：从串的尾部删除0个或多个符号后得到的串 (ban、banana、e) 后缀：从串的开始处删除0个或多个符号后得到的串 (nana、banana、e) 子串：删除串的某个前缀和某个后缀得到的串 (banana、nan、e) 真前缀、真后缀、真子串：既不等于原串，也不等于 空串的前缀、后缀、子串（前面例子的红色部分） 子序列：从原串中删除0个或者多个符号后得到的串 (baan) 11
串和语言 (2) • 和串有关的术语 (以banana为例) – 前缀：从串的尾部删除0个或多个符号后得到的串 (ban、banana、ε) – 后缀：从串的开始处删除0个或多个符号后得到的串 (nana、banana、ε) – 子串：删除串的某个前缀和某个后缀得到的串 (banana、nan、ε) – 真前缀、真后缀、真子串：既不等于原串，也不等于 空串的前缀、后缀、子串 (前面例子的红色部分) – 子序列：从原串中删除0个或者多个符号后得到的串 (baan) 11 南大编译许畅
串和语言(3) 串的运算 连接(Concatenation):x和y的连接是把y附加到x的后 面而形成的串，记作xy x=dog,y=house,xy=doghouse 指数运算（幂运算）：s0=E,s1=s,si=s-1s x=dog,xo=,x1=dog,x3=dogdogdog 12
串和语言 (3) • 串的运算 – 连接 (Concatenation)：x和y的连接是把y附加到x的后 面而形成的串，记作xy • x = dog，y = house，xy = doghouse – 指数运算 (幂运算)：s 0 = ε，s 1 = s，s i = s i-1 s • x = dog，x 0 = ε，x 1 = dog，x 3 = dogdogdog 12 南大编译许畅
串和语言(4) 。语言的运算 语言是某个给定字母表上的串的可数集合 运算 定义和表示 L和M的并 LUM={s|s属于L或者s属于.M} L和M的连接 LM={st|s属于L且t属于M} L的Kleene闭包 L*=U烂0L L的正闭包 L'=URLi 图3-6语言上的运算的定义 13
串和语言 (4) • 语言的运算 – 语言是某个给定字母表上的串的可数集合 13 + 南大编译许畅
串和语言（⑤） ·例子 L=A B.......b,....... -D={0,1,,9} LUD={AB,.,Z,a,b,..,z,0,1,,9} LD:520个长度为2的串的集合（字母+数字） L4:所有由四个字母构成的串的集合 L*:所有字母构成的集合，包括ε L (LD): D+:? 14
串和语言 (5) • 例子 – L = { A, B , ……, Z, a, b, ……, z } – D = { 0, 1, ……, 9 } – L D = { A, B, ……, Z, a, b, ……, z, 0, 1, ……, 9 } – LD：520个长度为2的串的集合 (字母 + 数字) – L4：所有由四个字母构成的串的集合 – L*：所有字母构成的集合，包括ε – L (L D)*：？ – D+：？ 14 南大编译许畅
正则表达式 字母表∑上的正则表达式的定义 基本部分 e是一个正则表达式，L(e)={e} 。如果a是Σ上的一个符号，那么a是正则表达式，L(a)={a} 归纳步骤 选择：(r)I(s),L(r)I(s)=L(r)UL(s) 连接：(r)s),L(r)s)=L(r)L(s) 闭包：(r),L(r)为=(L(r)i 括号：(r),L()》=L(r) 运算的优先级：*>连接>I,如(a)I(b)(c)=aIb*c 正则集合：可以用一个正则表达式定义的语言 15
正则表达式 • 字母表Σ上的正则表达式的定义 – 基本部分 • ε是一个正则表达式，L(ε) = { ε } • 如果a是Σ上的一个符号，那么a是正则表达式，L(a) = { a } – 归纳步骤 • 选择：(r)|(s)，L((r)|(s)) = L(r) L(s) • 连接：(r)(s)，L((r)(s)) = L(r)L(s) • 闭包：(r) * ，L((r) * ) = (L(r))* • 括号：(r)，L((r)) = L(r) • 运算的优先级：* > 连接 > |，如(a) | ((b)* (c)) = a | b* c • 正则集合：可以用一个正则表达式定义的语言 15 南大编译许畅