證明一種語言是正則語言的最普通的方法是為這種語言實際地建立起正則表達式。我們可以根據(jù)正則語言對于并運算、毗連運算、Kleene星號運算、補運算、交運算等都是封閉的這種特性來進行這樣的證明。如果能夠為一種語言中的兩個不同部分獨立地建立起正則表達式，就可以使用并運算的運算子為整個語言建立正則表達式，并且證明這種語言是正則語言。

有時，我們試圖證明一種語言不是正則語言。證明這種情況的最有用的工具是抽吸引理(pumping lemma）。這個引理的后面有兩種直覺，對于抽吸引理的描述來自Lewis and Papadimitriou（1981）以及Hopcroft and Ullman(1979）。第一個直覺是，如果一種語言能夠被有限狀態(tài)自動機模擬，那么我們必定能夠根據(jù)這種記憶約束量來判定任何符號串是不是在該語言中。這個記憶約束量對于不同的符號串不會增長得很大（因為對于給定的自動機，它的狀態(tài)數(shù)目是固定的），因此這個記憶量不一定與輸入的長度成比例。這意味著，諸如a?b?這樣的語言不可能是正則語言，因為這時我們需要某種辦法來記住n的數(shù)目，以便保證符號串中a的數(shù)量與b的數(shù)量相等。第二個直覺依賴于這樣的事實：如果一個正則語言具有任意長的符號串（比自動機中的狀態(tài)數(shù)還長），那么在該語言的自動機中必定會存在某種回路（loop）。我們可以使用這樣的事實說明，如果一種語言沒有這樣的回路，它就不是正則語言。

讓我們來研究一種語言L和與它相應(yīng)的確定有限自動機M，M具有N個狀態(tài)?？紤]輸入符號串的長度也是N。這個機器從狀態(tài)q0開始，在讀了一個符號之后進入狀態(tài)q1，在讀了N個符號之后進入狀態(tài)qn。換言之，長度為N的符號串將通過N+1個狀態(tài)（從狀態(tài)q0到狀態(tài)qN）。但是，在機器中只有N個狀態(tài)。這意味著，在接收的路徑上至少有兩個狀態(tài)必須是相同的（把它們稱為qi和qj）。換句話說，在從開始狀態(tài)到最后狀態(tài)的接收路徑上，必定存在回路。圖1說明了這種情況。設(shè)x是機器從開始狀態(tài)q0到回路起點的狀態(tài)qi讀的符號串，y是機器通過回路時讀的符號串，z是從回路終點qj到最后的接收狀態(tài)qN讀的符號串。

機器接收由這三個符號x,y和z構(gòu)成的毗連。但是，如果機器接收了xyz，那么它一定也接收xz！這是因為機器在處理xz時可以跳過回路，y就像被抽水機抽吸了一樣。另外，機器也可以在回路上打任意次數(shù)的圈兒，這樣它也就可以接收xyyz，xyyyz和xyyyyz等；這時，y又被放出來了。事實上，當n≥0時，它可以接收形式為xy?z的任何符號串。

圖1 具有N個狀態(tài)并且接收含有N個符號的符號串xyz的機器

這里給出的抽吸引理是有限狀態(tài)語言中的一種簡化版本。比較強的版本也可以應(yīng)用于有限狀態(tài)語言，但是它的抽吸引理的特定更明顯。