箱樊概悆有限的符号集合 进制{o,} ASCII Unicode 典型的字母表包括字母、数位和标点符号 串:字母表中符号组成的一个有穷序列 串s的长度|sl 空串,长度为o的串 ●语言:给定字母表上一个任意的可数的串的集合 语法正确的C程序的集合,英语,汉语
相关概念 字母表：一个有限的符号集合 二进制{0，1} ASCII Unicode 典型的字母表包括字母、数位和标点符号 串：字母表中符号组成的一个有穷序列 串s的长度 |s| 空串ε，长度为0的串 语言：给定字母表上一个任意的可数的串的集合 语法正确的C程序的集合，英语，汉语
相关概念(2) ●和串有关的术语( banana) 前缀:从串的尾部删除O个或多个符号后得到的串。(ban、 banana、￡) ●后缀:从串的开始处删除o个或多个符号后得到的串。 nana、 banana、 子串:删除串的某个前缀和某个后缀得到的串。( banana、 nan、) 真前缀、真后缀、真子串:既不等于原串,也不等于空串 的前缀、后缀、子串。 子序列:从原串中删除o个或者多个符号后得到的串。 (baan)
相关概念（2） 和串有关的术语（banana） 前缀：从串的尾部删除0个或多个符号后得到的串。（ban、 banana、 ε） 后缀：从串的开始处删除0个或多个符号后得到的串。 （nana、banana、ε） 子串：删除串的某个前缀和某个后缀得到的串。（banana、 nan、 ε） 真前缀、真后缀、真子串：既不等于原串，也不等于空串 的前缀、后缀、子串。 子序列：从原串中删除0个或者多个符号后得到的串。 （baan）
相关概念(3) 串的运算 ●连接 ( concatenation):x和y r的连接时把y附加到x的后面 形成的串,记作xy X=dog, y=house, xy=doghouse ●指数运算(幂运算):s=8,s=s,s=s-ls; Dog, X%=c, 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的并 LUM={s|s属于L或者s属于M} L和M的连接 LM={st|s属于L且t属于M} L的 Kleene闭包 L*=UO L L的正闭包 L* =U9, L
相关概念（4） 语言上的运算
语言及其运算示例3.3 L=A, B, .... Z, a, b ,....,Z D={o, 9 LUD:{A,B,…,Z,a,b,……,z,o,n1,g} LD:520个长度为的串的集合 L4:所有由四个字母构成的串的集合 L*:所有字母构成的集合,包括8。 LLUD D
语言及其运算示例3.3 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的串的集合 L 4：所有由四个字母构成的串的集合 L*：所有字母构成的集合，包括ε。 L(L U D): D+: