第二章语言及文法 主要内容 定义形式语言的术语 给出文法的定义和文法的分类 要求掌握: 语言和文法的形式定义 CHOMSKY文法体系的分类。 College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 1 第二章 语言及文法 ◼ 主要内容： ◼ 定义形式语言的术语 ◼ 给出文法的定义和文法的分类 ◼ 要求掌握： ◼ 语言和文法的形式定义 ◼ CHOMSKY文法体系的分类
第一节语言的定义与运算 、语言的一些术语: 字母表:字符的有限集合,记为T。 n字符串:由字母表T中的字符构成的序 列称字母表T上的字符串(句子)。 n常记为uy,Wyx,yz n常用a,b,c,d标识单个字符 College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 2 第一节 语言的定义与运算 一、语言的一些术语： ◼ 字母表： 字符的有限集合，记为T。 ◼ 字符串： 由字母表T中的字符构成的序 列称字母表T上的字符串（句子）。 ◼ 常记为u,v,w,x,y,z； ◼ 常用a,b,c,d 标识单个字符
字母表( Alphabet) ◇概念形式符号的集合 ◇记号常用T、∑表示 ◇举例 英文字母表{a,b,…,z,A,B,…,z} 英文标点符号表{,;:?! 汉字表{…自,…,动,…机,…} 化学元素表{H,He,Li,…,} T={a,n,y,任意} College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 3 字 母 表 （Alphabet） 概念 形式符号的集合 记号 常用 T、 表示 举例 − 英文字母表 a, b, …, z, A, B , …, Z − 英文标点符号表 , ; : . ? ! ’ ‘ “ ” ( ) … − 汉字表 …, 自, …, 动 , …, 机, … − 化学元素表 H, He, Li, …, − T = a, n, y, 任,意
字符串( string) ◇概念字母表T上的一个字符串(简称串),或称为 字(word),为T中字符构成的一个有限序列。 空串( empty string),用e表示,不包含任何 宇符。 举例设T={a,b},则E,a,ba, baba等都是串 ◇字符串w的长度,记为w,是包含在w中字符的 个数 举例|=0,|baba=5 a表示含有个a的字符串 College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 4 字 符 串 （string） 概念 字母表 T 上的一个字符串（简称串），或称为 字（word），为 T 中字符构成的一个有限序列。 空串（empty string）, 用 表示，不包含任何 字符。 举例 设 T = a, b ，则 , a, ba, bbaba 等都是串 字符串 w 的长度，记为 w ，是包含在 w 中字符的 个数 举例 = 0， bbaba = 5 a i 表示含有i个a的字符串
关于字符串的运算 ◇连接( concatenation) 设x,y为串,且X=a1a2…,amy=bb2…,bn 则x与y的连接 Xy=a1a2…amb1b2…bn ◇连接运算的性质 (xy)z=X(yz) EX=XE=X lx y=x+lyl College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 5 连接（concatenation） 设 x, y为串, 且 x = a1a2 … am, y = b1b2 … bn , 则 x 与 y 的连接 x y = a1a2 … am b1b2 … bn 连接运算的性质 − ( x y ) z = x（ y z ） − x = x = x − x y = x+y 关 于 字 符 串 的 运 算
关于字符串的运算 ◇其它如取头字符,取尾部,子串匹配等 设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, 任意