⑴ 正則語言，上下文無關語言，非上下文無關語言這三種怎麼判斷出來的
能使用
正則語言
寫出來或者DFA判別的就是正則語言
能使用上下文無關語言或者PDA判別的就是上下文無關語言
剩下的都是其他語言
正則語言和上下文無關語言可以使用
泵引理
判假，即所有正則語言，上下文無關均符合他們的泵引理，但是不是所有符合泵引理的都是CFG或者CFL
泵引理自行網路
⑵ 泵引理的引理應用
例1：字元串集合={ | m,n∈N ∧ n>m }不是正則的。
證明：顯然∈，所以由泵引理知當p足夠大時字元串中存在子串可重復。若該子串中只有0，那麼當k>1時將使得0多於1，這將導致矛盾。若同時存在0,1，那麼這將使0,1交替出現，同樣導致矛盾。若只出現1，由泵引理知k可為0，而此時將有1不多於0，這也是矛盾的。因此該語言不是正則的。
例2：若為所有素數的二進製表示的0,1串，那麼不是正則的。
證明：由初等數論易知存在任意大的素數，所以存在素數使得其二進制串長度大於泵引理閾值。將表示為，由泵引理知的二進制位串也屬於，因此也是素數。由費馬小定理知，所以即，又（即其可逆）所以。因此，所以| 這與為素數矛盾，故不是正則的。
⑶ 泵引理的引理描述
若 L 是正規語言，則存在一常數 n > 0 使得語言 L 中每個字串 w 的 |w| ≥ n，而當 w = xyz 時：
1.|xy| ≤ n ，
2.|y| ≥ 1 ，且
3.對所有的 k ≥ 0 ，字串 屬於 L 。
證：若L為正則語言，那麼存在一個DFA識別它。設其狀態數為n，那麼對於任意字元串w∈它被DFA識別時的狀態轉換為：（qn為接受狀態）。因為w≥ n，所以由鴿籠原理存在狀態重復，記狀態所識別的字元串為y，那麼易知（即是將重復狀態重復k次）仍可被此DFA識別，故∈。
⑷ 如何證明一個語言是正則語言
你是在學自動機這些東西嗎
只要有一個DFA或者NFA能夠表述這個預言 那麼他就是正則語言
DFA: 確定的有窮自動機
NFA： 不確定的有窮自動機
⑸ 怎樣運用泵引理證明能被4整除的整數是正則語言
一 封閉性
正則語言之並是正則的
正則語言之交是正則的
用自動機的乘積自動機。
如果證明了3，也可以用集合運算。
正則語言的補語言是正則的
用一個 DFA 表示原來的語言，然後把非接受狀態改為接受狀態，把接受狀態改為非接受狀態。
正則語言的差是正則的
集合運算。
正則語言的反轉是正則的
用一個 DFA A 表示原來的語言，把 A 改造成 RA, 先把所有箭頭反轉；把接受狀態改為普狀態；把初始狀態改為接受狀態。加入一個新狀態作為初始狀態，並發出 e 箭頭指向原來的全體接受狀態。
另一種方法是歸納。設語言為 L(A)，則 R(L(A)) = L(R(A))
正則語言的 kleene 閉包是正則的
正則語言的連接是正則的
二 應用舉例
設字元集合為 {0,1}. 語言 L 表示由不同個數的 0,1 組成的串, 試證明其為非正則的.
用泵引理證明 L 的補語言 L'={0,1 個數相同的串} 是非正則的. 從而 L' 的補語言 L 是非正則的.
⑹ 泵引理（形式語言與自動機理論）正規語言
形式語言 形式語言是一個字母表上的某些有限長字串的集合。一個形式語言可以包含無限多個字串。 語言的形式定義 字母表∑為任意有限集合,ε表示空串,記∑0為{ε},全體長度為n的字串為∑n,∑*為∑0∪∑1∪…∪∑n...