4语言 定义24: 给出字母表∑,则Σ上任一字符串集合,称为∑上的一个语 言,记为L,该语言的每一个字符串,便是语言L的一个语 句或句子。 例24设∑={a,b,c},则L={a,aa,ab,aa,ab,aba,abb,}为上 的一个语言,如果a表示字母,b表示数字,c看作其他符号 则L通常是程序语言中的标识符集。其中每个标识符便是标 识符集的一个句子。 由有限个字符串组成的集合为一有穷语言,反之为无 穷语言 6
6 4.语言 定义2.4 : 给出字母表，则上任一字符串集合，称为上的一个语 言，记为L，该语言的每一个字符串，便是语言L的一个语 句或句子。 [例2.4]设={a,b,c},则L={a,aa,ab,aaa,aab,aba,abb,…}为上 的一个语言，如果a表示字母，b表示数字，c看作其他符号, 则L通常是程序语言中的标识符集。其中每个标识符便是标 识符集的一个句子。 • 由有限个字符串组成的集合为一有穷语言，反之为无 穷语言
●对于字母表Σ,用∑*表示∑上所有字符串的集合 如∑={a,b},则Σ*={,a,b,ab,bb,ba…}。 显然∑上的任一语言L,都有Lc∑ 对于Σ,令∑+=∑*-{e},它是Σ上不含空串的字符串集合。 ●对于Σ的子集L,M,(它们都∑上的语言),可以定义下列 四种语言之间的运算。 定义25:语言L和M的连接,LM={xy|x∈ L and y∈M} 基于同一律,{ε}L=L{e}=L,除此而外,通常LM≠ML,即 连接不满足交换律,但满足结合律,即(LM)N=L(MN) 通常记L2=LL,并约定L。={E} 7
7 •对于字母表，用*表示上所有字符串的集合。 如={a,b}，则*={ ,a,b,aa,ab,bb,ba,…}。 显然上的任一语言L，都有L * 对于 ，令+=*-{}，它是上不含空串的字符串集合。 •对于*的子集L，M，(它们都上的语言)，可以定义下列 四种语言之间的运算。 定义2.5 :语言L和M的连接，LM={xy | x∈L and y∈M}。 基于同一律，{}L=L {}=L，除此而外，通常LM≠ML，即 连接不满足交换律，但满足结合律，即(LM)N=L(MN)。 通常记L²=LL,并约定Lº={}
定义26: 语言L和M的合并,LUM={x|x∈Lor|x∈M} 如同集合间的合并运算那样,它满足结合律,交换律。 定义27: 语言L的闭包,L*=L°UL∪L2UL3U.Ln。 定义28: 语言L的正闭包L+=LUL2UL3U.Ln。 如果Σ把看成是字母表Σ上长度为1的字符串集合,它当然也 是字母表∑上的一个语言,则是语言的自身连接,它也是上 的一个语言,特别令∑°={e},: ∑*=∑∪∑1U∑2Uz3U.∑n ∑+=∑1U∑2U∑3U..∑n 8
8 定义2.6 : 语言L和M的合并，L∪M={x | x∈L or | x∈M}。 如同集合间的合并运算那样，它满足结合律，交换律。 定义2.7 : 语言L的闭包，L*= Lº∪L¹∪L²∪L³∪…L ⁿ 。 定义2.8 : 语言L的正闭包L+= L¹∪L²∪L³∪…L ⁿ 。 如果把看成是字母表上长度为1的字符串集合，它当然也 是字母表上的一个语言，则是语言的自身连接，它也是上 的一个语言，特别令º= {}， ： 则 : *= º∪ ¹∪ ²∪ ³∪… ⁿ += ¹∪ ²∪ ³∪… ⁿ
「例25设字母集合L={a,b,c,…,,数字集合 D={0,1,,9},则 L∪D是字母数字集 LD是一个字母后跟一个数字的字符串集 L*是由字母组成的字符串(包括)集合。 L(L∪D)*是由字母开头的字母数字串的集合。 D+是长度大于等于1的数字串的集合
9 [例2.5]设字母集合L={a,b,c,…z}，数字集合 D={0,1,…9}，则 • L∪D是字母数字集 • LD是一个字母后跟一个数字的字符串集。 • L*是由字母组成的字符串（包括）集合。 • L(L∪D) *是由字母开头的字母数字串的集合。 • D+是长度大于等于1的数字串的集合
二、文法 1.文法的定义 定义29文法G是一个四元组,G=(Vt,vn,S,P),其中 Vt为终结符号集,这是个非空有限集; Vn为非终结符号集,它也是个非空有限集; S为一文法开始符,是一特殊的非终结符, P是产生式的非空有限集,其中每个产生式(或称规则)是 序偶,通常写作:a→β 或 读成是β或定义β为。a是产生式左部,β为产生式右部。 a都是由终结符和非终结符组成的符号串,只是a ∈(tUvn)+且至少有一个非终结符,而β∈(VUVn)*。 10
10 二、文法 1.文法的定义 定义2.9 文法G是一个四元组，G=(Vt,Vn,S,P) ，其中： Vt为终结符号集，这是个非空有限集； Vn为非终结符号集，它也是个非空有限集； S为一文法开始符，是一特殊的非终结符， P是产生式的非空有限集，其中每个产生式(或称规则)是一 序偶,通常写作：α→β 或 α::=β 读成α是β或α定义β为。 α是产生式左部， β为产生式右部。 α,β 都是由终结符和非终结符组成的符号串，只是α ∈(Vt∪Vn)+且至少有一个非终结符，而β∈(Vt∪Vn)*