●定理3-14已知产生一个非空语言的上下文无关 文法G=(∑,V,S,P),则文法中的每个非终结符都 是有用的;即:若A∈V,则S=>*uAv=>+uwv 其中:u,w,v∈∑ 证明: 读者自行完成
⚫ 定理3-14 已知产生一个非空语言的上下文无关 文法G=(∑,V,S,P)，则文法中的每个非终结符都 是有用的；即：若A∈V，则 S=>*uAv=>*uwv ⚫ 其中：u ，w ，v ∈∑* 。 ⚫ 证明： ⚫ 读者自行完成
●问题3-15上下文无关语言CFL是否有穷是否可 以判定? ●上下文无关文法CFG生成无穷个句子的原理是利 用递归的产生式,即 S=> uAy=>uv Axy=).>uviaxiy=)uviwxiy ●根据着一原理可以判定上下文无关语言是否有穷
⚫ 问题3-15 上下文无关语言CFL是否有穷是否可 以判定？ ⚫ 上下文无关文法CFG生成无穷个句子的原理是利 用递归的产生式，即 ⚫ S=>*uAy=>*uvAxy=>*…=>*uviAxiy=>*uviwxiy ⚫ 根据着一原理可以判定上下文无关语言是否有穷
定义3-16可派生性图的定义 上下文无关文法G=(∑,V,S,P),文法G的可 派生性图是满足下列条件的有向图: °(1)对于终结符或非终结符X,图中有且仅有一个 标记为X的顶点。 ●(2)如果A→>X1X2.Xn,则图中存在从标记为A的 顶点分别到标记为X1,X2,…,Xn的顶点的弧 ●(3)图中只有满足条件(1)和(2)的弧
⚫ 定义3-16 可派生性图的定义 ⚫ 上下文无关文法G=（∑，V，S，P），文法G的可 派生性图是满足下列条件的有向图： ⚫ (1)对于终结符或非终结符X，图中有且仅有一个 标记为X的顶点。 ⚫ (2)如果A->X1X2…Xn，则图中存在从标记为A的 顶点分别到标记为X1,X2,…,Xn的顶点的弧。 ⚫ (3)图中只有满足条件(1)和(2)的弧
●可派生性图表示了G中变量间的派生关系:从A到 B有一条有向路表示B出现在A派生出的某个符号 串中
⚫ 可派生性图表示了G中变量间的派生关系：从A到 B有一条有向路表示B出现在A派生出的某个符号 串中
●3.2推广的化简上下文无关文法 ●上下文无关文法化简的目的: 限制产生式的格式而不降低文法生成句子的能力, 从而降低文法分析算法的复杂度。 上下文无关文法化简的基本手段: 删除无用符号 删除单一产生式组
⚫ 3.2 推广的化简上下文无关文法 ⚫ 上下文无关文法化简的目的： 限制产生式的格式而不降低文法生成句子的能力， 从而降低文法分析算法的复杂度。 ⚫ 上下文无关文法化简的基本手段： 删除无用符号 删除单一产生式组