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