6.2形式语言的基本概念6.2.1基本定义1.字母表与问题有关的符号的有限集合，用V或又表示例: V =(A, B,C,.., Z) V, =(0, 1,2)2.句子由字母表中符号组成的有限长度的符号串，又称链。空句用入表示。组成：英文小写字母、数字。句子的长度：句子包含符号的数目，用表示，例：由V=a,b,c中元素可组成句子：重写次数lab3c3=9abc,aacc
6.2 形式语言的基本概念 6.2.1 基本定义 1．字母表 与问题有关的符号的有限集合，用V或∑表示。 2．句子 由字母表中符号组成的有限长度的符号串，又称链。空句 用λ表示。 组成：英文小写字母、数字。 例：由 V = {a, b, c} 中元素可组成句子： { , , , , } V1 = A B C Z {0, 1, 2} 例： V3 = abc，aacc，. 重写次数 句子的长度：句子包含符号的数目，用|•|表示。 | | 9 3 3 3 a b c =
3.语言由字母表中的符号根据某种文法组成的句子的集合V*：V中符号组成的所有句子的集合，包括空句：V+：不包含空句的句子集合。V+ =V*-{a)例：V*={a,ab,aabbcc,..Vt -fab, aabbcc,...4.文法构成一种语言的句子所必须遵守的规则G=(Vn,Vr, P, S)V：非终止符的有限集，子模式的集合，大写字母表示VT：终止符有限集，基元的集合，字母表起始部分的小写字母表示
3．语言 由字母表中的符号根据某种文法组成的句子的集合。 V * ：V中符号组成的所有句子的集合，包括空句； V +：不包含空句的句子集合。 { } * = − + V V { , , , } V * = ab aabbcc V = {ab, aabbcc, } 例： + 4．文法 构成一种语言的句子所必须遵守的规则。 G (V ,V , P, S ) = N T VN ：非终止符的有限集，子模式的集合，大写字母表示。 VT ：终止符有限集，基元的集合，字母表起始部分的小写 字母表示
终止符组成的字符串：用英文字母表尾部的小写字母x，y，V，w等表示，终止符和非终止符组成的混合字符串：用希腊字母α，β，等表示性质：VUV,=V（字母表）n=（空集）P：生成式的有限集。用文法产生句子时的重写规则P:α→βN替换字符串字符串S：起始符，代表模式本身，特殊的非终止符用生成式构成句子时，必须由左边是S的生成式开始
终止符和非终止符组成的混合字符串： 用英文字母表尾部的小写字母x，y，v，w等表示。 终止符组成的字符串： 用希腊字母α，β，γ等表示。 性质： VN VT =V （字母表） VN VT = （空集） P：生成式的有限集。用文法产生句子时的重写规则。 P： → 字符串 替换 字符串 S：起始符，代表模式本身，特殊的非终止符。 用生成式构成句子时，必须由左边是S的生成式开始
一种语言有一种文法，由文法G构成的语言用L（G）表示：L(G)=(x/xeV，且S=x福文法G的文法G构成的句子V-中字符组成的由终止符组成所有句子的集合推导关系"：零次或多次地应用推导关系=GS=x：句子x从起始符S开始利用文法G的生成式G经逐步推导得到
一种语言有一种文法，由文法G构成的语言用L(G)表示： ( ) { | , } * L G x x V S x G T = 且 文法G构成的句子 由终止符组成 VT中字符组成的 所有句子的集合 文法G的 推导关系 “ G ” ：零次或多次地应用推导关系 G “ S x G ”：句子 x 从起始符 S 开始利用文法 G 的生成式， 经逐步推导得到
例6.1 给定文法G=(V,VT,P,S)，其中V=A,B,S)V=a,b,cf，P的各生成式为S→aAc,②A→aAc,③A→B④BbB，?B-b判断x=aabcc是否属于语言L（G）？12解：是S三aAc三aaAccaaBcc三aabcc说明：利用文法构成句子时，除第一个生成式必须利用左边为起始符S的生成式外，其余生成式使用的先后次序及重复使用的次数都不受限制
例 6.1 给定文法 G (V ,V , P, S ) = N T ，其中 V {A, B, S} N = ， V {a, b, c} T = ，P 的各生成式为 ①S →aAc，② A→aAc，③ A → B ④ B →bB ，⑤ B →b 判断 x = aabcc 是否属于语言 L(G ) ？ S aAcaaAccaaBcc aabcc ① ② ③ ⑤ 利用文法构成句子时，除第一个生成式必须利用左边 为起始符 S 的生成式外，其余生成式使用的先后次序及重 复使用的次数都不受限制。 是 说明： 解：