抽吸引理：設(shè)L是一個有限的正則語言，那么必定存在著符號串x，y和z，使得對于n≥0，y≠ε并且xy?z∈L。

抽吸引理告訴我們，如果一種語言是正則語言，就存在著一個符號串y，這個y可以被適當(dāng)?shù)爻槲Ｈ欢?，這并不意味著，如果一種語言能夠?qū)τ谀硞€符號串進(jìn)行抽吸，這種語言就是正則語言。非正則的語言也會有符號串被抽吸，因此這個抽吸引理不能用來證明一種語言是正則語言。但是，抽吸引理可以用來證明某種語言不是正則語言，這時只需要證明，在某種語言中不能用適當(dāng)?shù)霓k法對符號串進(jìn)行抽吸。

現(xiàn)在，讓我們來證明，語言a?b?（也就是由n個a后面跟著同樣數(shù)目的b構(gòu)成的語言）不是正則語言。這時必須證明，我們?nèi)〉娜魏畏柎畇都不可能被分成x，y和z三個部分，使得y能夠被抽吸。隨意給一個由a?b?構(gòu)成的符號串s，可以用三種辦法來分割s，并且證明無論用哪種辦法，都不可能找到某個y能夠被抽吸。

1. y只由若干個a構(gòu)成。這意味著x也全都是由a組成的，z包含了全部b，而z的前面可能有若干個a。但是，如果y全都由a組成，就意味著xy?z中的a比xyz中的多。不過，這就意味著s中的a的數(shù)目比b的數(shù)目大，因而它不能成為a的成員！

2. y只由若干個b構(gòu)成。這種情況與上面的相似。如果y全都由b組成，就意味著xy?z中的b比xyz中的多，因此，s中的b的數(shù)目比a的數(shù)目多。

3. y由若干個a和若干個b構(gòu)成。這意味著x只包含a,y只包含b。這時，xyz必定有一些b在a之前，因此，它不可能成為a?b?的成員！

由此可見，在a?b?中沒有符號串能夠被分割為x,y和z,使得y能夠被抽吸。所以，a?b?不是正則語言。

a?b?不是正則語言，但是a?b?是上下文無關(guān)語言。實際上，上下文無關(guān)語法只需要兩條規(guī)則就可以給a?b?建立模型，這兩條規(guī)則是：

S→a S b

S→ε

圖2是使用這個語法推導(dǎo)句子aabb的剖析樹。

上下文無關(guān)語言也有一個抽吸引理，這個引理可用來鑒別一種語言是不是上下文無關(guān)的，詳細(xì)的討論可參閱Hopcroft and Ullman(1979)和Partee et al.(1990)。

圖2 aabb的上下文無關(guān)剖析樹

責(zé)任編輯：admin