小练习:学员可证明算符文法有如下两个性质。
  性质1 在算符文法中任何句型都不包含两个相邻的非终结符 。
  性质2 如果Ab或(bA)出现在算符文法的句型γ中,其中A∈VN ,b∈VT,则γ中任何含b的短语必含有A。
  参考答案:
  证明:性质1
  用归纳法
  设γ是句型,即Sγ
  S=ω0ω1 ... ωn-1ωn
  推导长度为n,归纳起点n=1时,
  S=ω0ω1=γ,即Sγ,必存在产生式S→γ,而由算符文法的定义,文法的产生式中无相邻的非终结符,显然满足性质1。
  假设n>1, ωn-1满足性质1。
  若ωn-1=αAδ,A为非终结符。
  由假设α的尾符号和δ的首符号都不可能是非终结符,否则与假设矛盾。
  又若A→β是文法的产生式,则有
  ωn-1ωn=αβδ=γ
  而A→β是文法的原产生式,不含两个相邻的非终结符,所以αβγ也不含两个相邻的非终结符。满足性质1。证毕。
  证明:性质2
  用反证法。
  因为由算符文法的性质1知可有:
  Sγ=αbAβ
  若存在Bαb,这时b和A不同时归约,则必有SBAβ,这样在句型BAβ中存在相邻的非终结符B和A,所以与性质1矛盾,证毕。注意:含b的短语必含A,含A的短语不一定含b。