化简的上下文无关文法 ●左线性文法和右线性文法是线性文法中 特殊的两类
化简的上下文无关文法 ⚫ 左线性文法和右线性文法是线性文法中 特殊的两类
●定理32G=(∑,V,S,P)是一个上下文 无关文法,产生式的一般形式为A→W,其中 W∈(xUV)·, 则存在另一个等价的线性的无关文法G1,而 G1中产生式的形式为; A>a或A-aβb 其中:A∈v;a,b∈∑u{e};β∈v
⚫ 定理3-2 G=（∑，V，S，P）是一个上下文 无关文法，产生式的一般形式为A→w，其中： w∈（∑UV）* ， ⚫ 则存在另一个等价的线性的无关文法G1，而 G1中产生式的形式为； ⚫ A→a 或 A→aβb。 ⚫ 其中: A∈V；a，b∈∑U{ε} ；β∈V+
●证明: 读者自己完成
⚫ 证明： ⚫ 读者自己完成
定理33G=(∑,V,s,P)是一个上下文 无关文法,产生式的一般形式为A→W,其 中:w∈(∑Uv)‘,则存在另一个等价的无 关文法G1,而G1中产生式的形式为; A→a或A→aB或A→aBC。 其中:A,B,cev;a∈∑{} ●证明:读者自己完成
⚫ 定理3-3 G=（∑，V，S，P）是一个上下文 无关文法，产生式的一般形式为A→w，其 中：w∈（∑UV）* ，则存在另一个等价的无 关文法G1，而G1中产生式的形式为； ⚫ A→a 或 A→aB 或 A→aBC。 ⚫ 其中：A ，B，C∈V；a∈∑ {ε} 。 ⚫证明： 读者自己完成
3.1消除无关文法中的无用非终结符号 定义3-4文法中的无用符号 个无关文法G,符号Y∈V,如果不出 现在任何形如S=>uY=>uW的推导 之中,称Y为文法G的无用非终结符。 其中:u,W,V∈∑
3.1 消除无关文法中的无用非终结符号 ⚫ 定义3-4 文法中的无用符号 ⚫ 一个无关文法G,符号Y∈V,如果不出 现在任何形如S=>*uYv=>* uwv的推导 之中，称Y为文法G的无用非终结符。 ⚫ 其中：u ，w ，v ∈∑*