●对于一个上下文无关文法G,如果: ●①没有A→A形式的产生式; ●②每个非终结符A都是有用的,即 有S=>*aAB=>*awB; ●其中:α,w,B∈∑*; 则该文法是化简的上下文无关文法
⚫ 对于一个上下文无关文法G，如果： ⚫ ① 没有A→A形式的产生式； ⚫ ② 每个非终结符A都是有用的，即： ⚫ 有S=>*αAβ=>*αwβ； ⚫ 其中：α，w，β∈∑* ； ⚫ 则该文法是化简的上下文无关文法
●对于任意的无关文法,进行 (1)直接删除没有A→A形式的产生式 ●对于A→A形式的产生式,该类产生式是递归的,可以反 复利用任意多次,但对于无穷语言的产生,没有任何作 用。可以直接删除即可。 (2)消除无关文法中的无用非终结符号 消除无关文法中的无用非终结符号后,无关文法中的所 有非终结符号都是有用的。 得到的文法是化简的上下文无关文法
⚫ 对于任意的无关文法，进行 ⚫ （1）直接删除没有A→A形式的产生式 ⚫ 对于A→A形式的产生式，该类产生式是递归的，可以反 复利用任意多次，但对于无穷语言的产生，没有任何作 用。可以直接删除即可。 ⚫ （2）消除无关文法中的无用非终结符号 ⚫ 消除无关文法中的无用非终结符号后，无关文法中的所 有非终结符号都是有用的。 ⚫ 得到的文法是化简的上下文无关文法
●定义3-21推广的简化上下文无关文法: ●对于一个上下文无关文法G,如果该文法中不存 在形如A→B的产生式(A,B∈V), ●则该文法是推广的化简上下文无关文法
⚫ 定义3-21 推广的简化上下文无关文法： ⚫ 对于一个上下文无关文法G，如果该文法中不存 在形如A → B的产生式（A，B ∈ V ）， ⚫ 则该文法是推广的化简上下文无关文法
●定理3-22对于一个上下文无关文法G,能够找 到一个等价的无关文法G1,而G1中不存在形如A →B的单产生式(A,B∈V) ●证明思路: ●对于某个推导过程: S=X*aab=abb=>awB=> 可简化为:S=>*aAB=>aW1B= ●即省略掉A=>B的推导
⚫ 定理3-22 对于一个上下文无关文法G，能够找 到一个等价的无关文法G1，而G1中不存在形如A → B的单产生式（A，B ∈ V ）。 ⚫ 证明思路： ⚫ 对于某个推导过程： S=>*αAβ=>αBβ=>αwIβ=>… ⚫ 可简化为：S=>*αAβ=>αwIβ=>… ⚫ 即省略掉A => B的推导
●因此,需要将A→B的产生式使用下面产生式进行 替换: A→W1|W2w3..|wn 而B→W1w2W3..Wwn是文法G中关于B的所有 产生式
⚫ 因此，需要将A→B的产生式使用下面产生式进行 替换： ⚫ A →w1 |w2 |w3 |…|wn ⚫ 而B →w1 |w2 |w3 |…|wn 是文法G中关于B的所有 产生式