抽吸引理：设L是一个有限的正则语言，那么必定存在着符号串x，y和z，使得对于n≥0，y≠ε并且xyⁿz∈L。

抽吸引理告诉我们，如果一种语言是正则语言，就存在着一个符号串y，这个y可以被适当地抽吸。然而，这并不意味着，如果一种语言能够对于某个符号串进行抽吸，这种语言就是正则语言。非正则的语言也会有符号串被抽吸，因此这个抽吸引理不能用来证明一种语言是正则语言。但是，抽吸引理可以用来证明某种语言不是正则语言，这时只需要证明，在某种语言中不能用适当的办法对符号串进行抽吸。

现在，让我们来证明，语言aⁿbⁿ（也就是由n个a后面跟着同样数目的b构成的语言）不是正则语言。这时必须证明，我们取的任何符号串s都不可能被分成x，y和z三个部分，使得y能够被抽吸。随意给一个由aⁿbⁿ构成的符号串s，可以用三种办法来分割s，并且证明无论用哪种办法，都不可能找到某个y能够被抽吸。

1. y只由若干个a构成。这意味着x也全都是由a组成的，z包含了全部b，而z的前面可能有若干个a。但是，如果y全都由a组成，就意味着xyⁿz中的a比xyz中的多。不过，这就意味着s中的a的数目比b的数目大，因而它不能成为a的成员！

2. y只由若干个b构成。这种情况与上面的相似。如果y全都由b组成，就意味着xyⁿz中的b比xyz中的多，因此，s中的b的数目比a的数目多。

3. y由若干个a和若干个b构成。这意味着x只包含a,y只包含b。这时，xyz必定有一些b在a之前，因此，它不可能成为aⁿbⁿ的成员！

由此可见，在aⁿbⁿ中没有符号串能够被分割为x,y和z,使得y能够被抽吸。所以，aⁿbⁿ不是正则语言。

aⁿbⁿ不是正则语言，但是aⁿbⁿ是上下文无关语言。实际上，上下文无关语法只需要两条规则就可以给aⁿbⁿ建立模型，这两条规则是：

S→a S b

S→ε

图2是使用这个语法推导句子aabb的剖析树。

上下文无关语言也有一个抽吸引理，这个引理可用来鉴别一种语言是不是上下文无关的，详细的讨论可参阅Hopcroft and Ullman(1979)和Partee et al.(1990)。

图2 aabb的上下文无关剖析树

责任编辑：admin