串和语言(2) 和串有关的术语( bannana) 前缀:从串的尾部删除0个或多个符号后得到的串。 (ban、 banana、ε) 后缀:从串的开始处删除0个或多个符号后得到的 串。(nana、 banana、ε) 子串:删除串的某个前缀和某个后缀得到的串。 ( banana、nan、ε) 真前缀、真后缀、真子串:既不等于原串,也不等 于空串的前缀、后缀、子串。(前面例子的红色部 子序列:从原串中删除0个或者多个符号后得到的 串。(baan)
串和语言（2） • 和串有关的术语（bannana） – 前缀：从串的尾部删除0个或多个符号后得到的串。 （ban、banana、 ε） – 后缀：从串的开始处删除0个或多个符号后得到的 串。（nana、banana、ε） – 子串：删除串的某个前缀和某个后缀得到的串。 （banana、nan、 ε） – 真前缀、真后缀、真子串：既不等于原串，也不等 于空串的前缀、后缀、子串。（前面例子的红色部 分） – 子序列：从原串中删除0个或者多个符号后得到的 串。（baan）
串和语言(3) 串的远算 连接( concatenation):x和y的连接时把y附加到x 的后面形成的串,记作Xyo Dog, y=house, xy=doghouse 指数运算(幂运算):s=ε,s=s,s=sls; Xdog, x=E, X=dog, X-dogdogdog
串和语言（3） • 串的运算 – 连接(concatenation)：x和y的连接时把y附加到x 的后面形成的串，记作xy。 • x=dog，y=house，xy=doghouse – 指数运算（幂运算）：s 0=ε，s 1=s，s i=si-1 s； • x=dog，x 0=ε，x 1=dog，x 3=dogdogdog
串和语言(4) 语言的远算 运算 定义和表示 L和M的并 L∪M={8|s属于L或者8属于M} L和M的连接 LM={8t|8属于L且t属于M} L的Klee闭包 L*=Uo LZ L的正闭包 L* =U,L 图3-6语言上的运算的定义
串和语言（4） • 语言的运算
串和语言(5) 例子 L={AB,……Zab,……,2z} D={0,129} LUD={AB,…Z,a.b,20 LD:520个长度为2的串的集合 L4:所有由四个字母构成的串的集合 L*:所有字母构成的集合,包括8 LL UD, D
串和语言（5） • 例子 – L={A,B,……,Z,a,b,……,z} – D={0,1,……,9} – L U D={A,B,……,Z,a,b,……,z,0,1,……,9} – LD：520个长度为2的串的集合 – L4：所有由四个字母构成的串的集合 – L*：所有字母构成的集合，包括ε。 – L(L U D)，D+
正则表达式 宁母表∑上的正则表达式的定义 基本部分 E是一个正则表达式,L()={e} 如果a是Σ上的一个符号,那么a是正则表达式,L(a)={a} ·归纳步骤 选择:(〔r)|(s),L(r)|(s)L(r)UL(s) 连接:(r)(s,L(r)(S)=L(r)L(S); 闭包:(r)*,L(〔)*)=(L(r)* 括号:(r),L(r)=L(r) ·运算的优先级:*>连接> ·正则集合:可以用一个正则表达式定义的语言
正则表达式 字母表Σ上的正则表达式的定义 • 基本部分 – ε 是一个正则表达式，L(ε)={ε} – 如果a是Σ上的一个符号，那么a是正则表达式，L(a)={a} • 归纳步骤： – 选择：(r) | (s)，L((r) | (s))=L(r) U L(s)； – 连接：(r)(s)，L((r)(s))=L(r)L(s) ； – 闭包：(r)* ，L((r)*)=(L(r))*； – 括号：(r)，L((r))=L(r) • 运算的优先级：* > 连接 > | • 正则集合：可以用一个正则表达式定义的语言