小练习：学员可证明算符文法有如下两个性质。 　　性质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。