形式语言与自动机语言及文法.ppt

College of Computer Science Technology, BUPT 形式语言与自动机课件语言及文法 第1页，共35页。 * College of Computer Science Technology, BUPT 第一节 语言的定义与运算 一、语言的一些术语： 字母表： 字符的有限集合，记为T。 字符串： 由字母表T中的字符构成的序列称字母表T上的字符串（句子）。 常记为u,v,w,x,y,z； 常用a,b,c,d 标识单个字符。 第2页，共35页。 * College of Computer Science Technology, BUPT 字 母 表 （Alphabet） 概念 形式符号的集合 记号 常用 T、 ? 表示 举例 英文字母表 ? a, b, …, z, A, B , …, Z ? 英文标点符号表 ? , ; : . ? ! ’ ‘ “ ” ( ) … ? 汉字表 ? …, 自, …, 动 , …, 机, … ? 化学元素表 ? H, He, Li, …, ? T = ? a, n, y, 任,意 ? 第3页，共35页。 * College of Computer Science Technology, BUPT 字 符 串 （string） 概念 字母表 T 上的一个字符串（简称串），或称为 字（word），为 T 中字符构成的一个有限序列。 空串（empty string）, 用? 表示，不包含任何 字符。 举例 设 T = ? a, b ?，则? , a, ba, bbaba 等都是串 字符串 w 的长度，记为 ?w? ，是包含在 w 中字符的个数 举例 ?? ? = 0， ?bbaba? = 5 ai 表示含有i个a的字符串 第4页，共35页。 * College of Computer Science Technology, BUPT 连接（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? 关 于 字 符 串 的 运 算 第5页，共35页。 * College of Computer Science Technology, BUPT 其它 如 取头字符，取尾部，子串匹配 等 设ω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 ε, 即一个字符串可以看作是多个字符串的连接。 关 于 字 符 串 的 运 算 第6页，共35页。 * College of Computer Science Technology, BUPT 字符串ω的逆用 表示。 是字符串ω的倒置。 ω= b1b2……bn = bnbn-1……b2b1 空串ε的逆还是ε 第7页，共35页。 * College of Computer Science Technology, BUPT 字 母 表 的 幂 运 算 幂运算 设 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* ? ? ? ? 第8页，共35页。 * College of Computer Science Technology, BUPT 闭包的物理意义 T的星号闭包T*：字母表T上的所有字符串和空串的集合。 T的正闭包T+：字母表T上的所有字符串构成的集合。 T*= T+∪{ε} 举例 设 T = ? 0，