符号串集合的运算p21 o符号串集V的闭包V* V*=VOU V1 U V2 U V3 U. 0 设V={a,b},则 V*={8}Ufa,b}Ufaa,ab,ba,bb}U. ={8,a,b,aa,ab,ba,bb,aaa,. oV的闭包V*是V上的所有符号串（包括空字e)的集合 o符号串集V正闭包V V+=V1 U V2 U V3 U.=VV* o设V={a,b},则 V+={a,b}U[aa,ab,ba,bb}U. ={a,b,aa,ab,ba,bb,aaa,. oV的正闭包V+是V上的所有的非空符号串的集合 20
20 符号串集合的运算 p21 符号串集V的闭包 V * V * =V0∪ V1 ∪ V2 ∪ V3 ∪. 设V={a，b}，则 V * ={ε}∪{a，b} ∪{aa，ab，ba，bb}∪. ={ε，a，b，aa，ab，ba，bb，aaa，.} V的闭包V *是V上的所有符号串(包括空字ε)的集合 符号串集V正闭包 V + V + = V 1 ∪ V2 ∪ V3 ∪. =V V * 设V={a，b}，则 V + ={a，b} ∪{aa，ab，ba，bb}∪. ={a，b，aa，ab，ba，bb，aaa，.} V的正闭包V +是V上的所有的非空符号串的集合
语言的概念 0语言 某个字母表∑上的符号串集合，是∑*的 一个子集 口例∑={0,1 0 ∑*={e,0,1,00,01,10,11,000,001,.} 口则 {1,11,111,1111,.}是一种语言 章节目录 迎 2】 国回
21 语言的概念 语言 某个字母表∑上的符号串集合，是∑*的 一个子集 例 ∑={0，1} ∑* = {ε,0,1,00,01,10,11,000,001,.} 则 {1,11,111,1111,.}是一种语言 章节目录
2.3文法和语言的形式定义p21 口规则或产生式 加文法的定义 口（直接）推导和（直接）归约 加句型和句子 口文法描述的语言 口▣文法的等价性 ☑) 22
22 2.3 文法和语言的形式定义 p21 规则或产生式 文法的定义 (直接)推导和 (直接)归约 句型和句子 文法描述的语言 文法的等价性
规则或产生式p21 o形式 0a→B或a::=B ▣a称为产生式的左部 口B称为产生式的右部 口读作“a定义为B” 口举例 oA→a这是关于A的 一条规则 〈标识符〉→〈字母〉 <字母>→ab.|z 迎 23 ☒2
23 规则或产生式 p21 形式 α→β或α::=β α称为产生式的左部 β称为产生式的右部 读作“α定义为β” 举例 A→a 这是关于A的一条规则 <标识符> →<字母> <字母> →a|b|.|z
文法G的形式定义p22 G=(VT,VN,S,P) Chomsky定义文法为一个四元式 ▣Vr非空有穷终结符集 oVN非空有穷非终结符集VT∩VN= S∈VN开始符号 口S至少在产生式左部出现一次 口P非空有穷产生式集合a→B 口a∈(VT U VN)*,且至少含有一个非终结符 oB∈(VT UVN)*, o令V=VT UVN 口称V为文法符号，是文法G的字母表 24
24 文法G的形式定义 p22 Ｇ = (ＶT，ＶN，S，P) Chomsky定义文法为一个四元式 ＶT 非空有穷终结符集 ＶN 非空有穷非终结符集 ＶT ∩ＶN = ф Ｓ∈ＶN 开始符号 S至少在产生式左部出现一次 Ｐ非空有穷产生式集合 α→β α∈(ＶT ∪ＶN) * ，且至少含有一个非终结符 β∈(ＶT ∪ＶN) * ， 令Ｖ=ＶT ∪ＶN 称Ｖ为文法符号，是文法G的字母表