关于字符串的运算 ◇其它如取头字符,取尾部,子串匹配等 设1,U2,03是字母表T上的字符串,称u1是字符 串ω102的前缀,2是字符串u1u2的后缀,且u2 是字符串1002u3的子串 n空串是任何字符串的前缀,后缀及子串。 例 abc的前缀 a ab abc s. 后缀 c bc abc e. 子串 a b c ab bc abc s, 即一个字符串可以看作是多个字符串的连接。 College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 6 其它 如 取头字符，取尾部，子串匹配 等 ◼ 设ω1, ω2, ω3是字母表T上的字符串，称ω1是字符 串ω1ω2的前缀，ω2是字符串ω1ω2的后缀，且ω2 是字符串ω1ω2ω3的子串。 ◼ 空串是任何字符串的前缀，后缀及子串。 ◼ 例： abc的前缀 a ab abc ε. 后缀 c bc abc ε. 子串 a b c ab bc abc ε, 即一个字符串可以看作是多个字符串的连接。 关 于 字 符 串 的 运 算
字符串ω的逆用矿表示。是字符 串ω的倒置。 =b1b2……bn a =bnbni-..b2b, n空串的逆还是E College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 7 ◼ 字符串ω的逆用 表示。 是字符 串ω的倒置。 ω= b1b2……bn = bnbn-1……b2b1 ◼ 空串ε的逆还是ε
字母表的幂运算 ◇幂运算设T为字母表,n为任意自然数, 定义(1)T={c} (2)设ⅹ∈Tn1,a∈T,则ax∈Tn (3)T中的元素只能由(1)和(2)生成 ◇*闭包T=T0∪T1uT2U ◇+闭包T+=T1∪T2UT3∪ ◇T*=T∪{G},T=T-{G} College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 8 字 母 表 的 幂 运 算 幂运算 设 T 为字母表，n 为任意自然数， 定义（1） T0 = （2）设 x Tn-1 ，a T， 则a x Tn （3） Tn 中的元素只能由（1）和（2）生成 闭包 T* = T0 T1 T2 … + 闭包 T+ = T1 T2 T3 … T* = T+ ， T+ = T* −
闭包的物理意义 ◇T的星号闭包T*:字母表T上的所有字符串和空串的集 ◇T的正闭包T+:字母表T上的所有字符串构成的集合。 T=T+UE ◇举例设T={0,1},则 T0={},T={0,1} T2={00,01,10,11} T*={E,0,1,00,01,10,11,…} T={0,1,00,01,10,11,…} College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 9 闭包的物理意义 T的星号闭包T*：字母表T上的所有字符串和空串的集 合。 T的正闭包T+：字母表T上的所有字符串构成的集合。 T*= T+∪{ε} 举例 设 T = 0，1 ，则 T0 = ， T1 = 0，1 ， T2 = 00，01 ，10 ，11 ， … T* = ，0，1，00，01 ，10 ，11，… T+ = 0，1，00，01 ，10 ，11，…
语言( LANGUAGES) ◇欐念设T苟字母森,则任何集合LgT是字母 表T上的一个语言( language) ◇举例 英文单词集{… English,…, words,…} C语言程序集{ 字母森? 汉语咸语集{…,马到咸功,…} 化学分子式集{…,H2O,…,NaC,…} any,任意} College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 10 语 言 （Languages） 概念 设 T 为字母表，则任何集合 L T* 是字母 表T上的一个语言（language） 举例 − 英文单词集 …, English, …, words , … − C 语言程序集 … 字母表？ − 汉语成语集 …, 马到成功, … − 化学分子式集 …, H2O, …, NaCl , … − any, 任意