32语言和文法 例L3={ambn≥1}的上下文有关文法 S→aSBC S→aBC CB→BC aB→)ab bB→)bb bC→bc CC→cc abc的推导过程如下: S→*mn1S(BCn1用S→ a Sbc n-1次 S→+u"(BC 用S→>aBC1次 S→+a"BCn 用CB→>BC交换相邻的CB S→+abBn-1C 用aB→mb1次 S→+abCn 用bB→bbn-1次 S→+ ancoN-1 用bC→bc1次 S→+ anb"cnl 用cC→ccn-1次3.2 语言和文法 • 例 L3 ＝{a nb nc n | n  1}的上下文有关文法 S → aSBC S → aBC CB → BC aB → ab bB → bb bC → bc cC → cc a nb nc n的推导过程如下： S * a n-1S(BC) n−1 用S → aSBC n-1次 S + a n (BC) n 用S → aBC 1次 S + a nBnCn 用CB → BC交换相邻的CB S + a nbBn−1Cn 用aB → ab 1次 S + a nb nCn 用bB → bb n-1次 S + a nb ncCn-1 用bC → bc 1次 S + a nb nc n 用cC → cc n-1次