●注意: 个语言包含有空串ε或语言本身就是{e},它 们都不是空集Φ
⚫ 注意： ⚫ 一个语言包含有空串ε或语言本身就是{ε}，它 们都不是空集Ф
●判定方法: ●①首先使用空串定理,消除该无关文法中的所有 空串产生式,如果还有S→ε,则该文法产生的 语言不为空 ●(2)构造能产生终结符串的非终结符集合N,如果 S∈N,则该文法产生的语言不为空。否则,该 文法产生的语言为空
⚫ 判定方法： ⚫ ①首先使用空串定理，消除该无关文法中的所有 空串产生式，如果还有S→ε，则该文法产生的 语言不为空； ⚫ (2)构造能产生终结符串的非终结符集合N，如果 S ∈ N，则该文法产生的语言不为空。否则，该 文法产生的语言为空
●定理3-11已知产生一个非空语言的上下文无关 文法G,则对于某个A∈V,总有A=*w,且 W∈∑*。 证明 读者自行完成
⚫ 定理3-11 已知产生一个非空语言的上下文无关 文法G，则对于某个A ∈ V，总有A=>*w，且 w∈∑* 。 ⚫ 证明： ⚫ 读者自行完成
定理3-12一个无关文法G=(∑,V,S,P),产生的语言为 LG)。如果L(G)不为空,则至少存在一个非终结符A,而 它的产生式右边仅仅只包含终结符号或空串e。 ●证明提示: 考虑产生串的推导过程中最后使用的产生式的特点。 证明: 读者自行完成
⚫ 定理3-12 一个无关文法G=(∑,V,S,P)，产生的语言为 L(G)。如果L(G)不为空，则至少存在一个非终结符A，而 它的产生式右边仅仅只包含终结符号或空串ε 。 ⚫ 证明提示： ⚫ 考虑产生串的推导过程中最后使用的产生式的特点。 ⚫ 证明： ⚫ 读者自行完成
●定理3-13已知产生一个非空语言的上下文无关 文法G=(∑,V,S,P),则能够构造一个等价 的无关文法G1,对于任意A∈V,总有一个推 导:S=>*w1AW2=>*W1W2W2,且W,W2,W2∈∑ 证明: 读者自行完成
⚫ 定理3-13 已知产生一个非空语言的上下文无关 文法G=（∑，V，S，P），则能够构造一个等价 的无关文法G1，对于任意A ∈ V，总有一个推 导:S=>*w1 Aw3 =>*w1 w2 w3，且w1，w2，w3 ∈∑* 。 ⚫ 证明： ⚫ 读者自行完成