文法：
認(rèn)識(shí)終結(jié)符和非終結(jié)符
? ? ? ? 終結(jié)符? ? ? ? ? ? ? ? ? 非終結(jié)符
? ? （小寫，不可再分元素）? ? ? （大寫，可再分元素）
例如：
有文法G2[S]為
? ? S->Ap
? ? S->Bq
? ? A->a
? ? A->cA
? ? B->b
? ? B->dB
? ? 這里S為開始符，S,A,B為非終結(jié)符，而p,q,a,b,c,d為終結(jié)符
注意：終結(jié)符不能單獨(dú)在左邊，即a->b 這是錯(cuò)誤的。a不能單獨(dú)在左邊；
文法類型：
? ? *? 0型文法
? ? *? 1型文法
? ? *? 2型文法
? ? *? 3型文法
0型文法：
? ? 設(shè)（Vn,Vt,P,S），如果它的每個(gè)產(chǎn)生式 α->β 是這樣的一種結(jié)構(gòu)：
? ? α∈（Vn ∪ Vt）*? '（且至少含有一個(gè)非終結(jié)符)'，而β∈（Vn ∪ Vt）*.則G是一個(gè)0型文法。
? ? （
? ? ()*稱為閉包，
? ? Vn:非終結(jié)符集合，
? ? Vt:終結(jié)符集合，
? ? P:推導(dǎo)式集合，
? ? S:開始符
? ? ）
? ? 0型文法也稱 “ 短語文法 ”。一個(gè)非常重要的理論結(jié)果是：0型文法相當(dāng)于圖靈機(jī)（Turing）。
? ? 或者說，任何0型文法語言都是遞歸可枚舉的，反之，遞歸可枚舉集必定是一個(gè)0型文法；
? ? 0型文法是這幾類文法中，限制最少的一個(gè)。所以我們?cè)谠囶}中見到的，至少是0型文法
? ? 例如上面的G2[S]文法
? ? S,A,B? p,q,a,b,c,d都屬于（Vn ∪ Vt）*
? ? Sa,BacB，Ab,AB,SA,abc組合元素也屬于（Vn ∪ Vt）*
? ? 一個(gè)串的所有元素都∈（Vn ∪ Vt），不管這個(gè)串多長(zhǎng)，它都屬于（Vn ∪ Vt）*
? ? 所以:G2[S]文法屬于0型文法.
1型文法：
? ? 1型文法也叫上下文有關(guān)文法，此文法對(duì)應(yīng)于線性有界自動(dòng)機(jī)。它是在0型文法的基礎(chǔ)上每一個(gè)α->β,
? ? 都有 |α|->|β|? ，這里的|β|表示的是β的長(zhǎng)度。
? ? 注意：雖然要求 |β| >= |α|,但有一特例，α->? 也滿足1型文法。
? ? 例如 A->Ba , 則|β|=2,|α|=1符合1型文法要求。反之，如aA->a，則不符合1型文法。
2型文法：
? ? 2型文法也叫上下文無關(guān)文法，它對(duì)應(yīng)于下推自動(dòng)機(jī)。2型文法是在1型文法的基礎(chǔ)上，再滿足：
? ? 每一個(gè) α->β 都有α是非終結(jié)符。
? ? 例如A->Ba，符合2型文法要求。
? ? 如：Ab->Bab 雖然符合1型文法要求，但不符合2型文法要求，因?yàn)槠洇?Ab，而Ab不是一個(gè)非終結(jié)符，如何AB則為一個(gè)非終極符
3型文法：
? ? 3型文法也叫正規(guī)文法，它對(duì)應(yīng)于有限狀態(tài)自動(dòng)機(jī)，它是在2型文法的基礎(chǔ)上滿足：A->α|αB (右線性)或A->α|Bα (左線性)
? ? 如有：A->a，A->aB，B->a，B->cB，則符合3型文法的要求
? ? 但如果推導(dǎo)為：
? ? ? ? ? ? A->ab，A->aB，B->a,B->cB
? ? 或推導(dǎo)為：
? ? ? ? ? ? A->a，A->Ba，B->a，B->cB
? ? ? ? ? ? 則不符合3型文法的要求了。
? ? 要不全部統(tǒng)一右線性，要不全部統(tǒng)一左線性，才符合3型文法的要求；
? ? 左右線性混合不符合3型文法的要求
? ? 3型文法 （含于） 2型文法 （含于） 1型文法 （含于） 0型文法
? ? 例題：
? ? 有文法G為：
? ? ? ? A->∑|aB
? ? ? ? B->Ab|a
? ? 請(qǐng)判斷文法G屬于哪一類文法？
? ? ? ? 首先看到 |，先把文法拆分出來,得到
? ? ? ? ? ? A->∑? ? A->aB
? ? ? ? ? ? B->Ab? B->a
? ? ? ? 從0型文法開始算起；
? ? ? ? 所以文法G屬于2型文法，不屬于3型文法
? ? 例題：
? ? 在文法G=（Vn,Vt,P,S）,G=（{S,A,B},{0,1},P,S）中，P的生成式有:
? ? ? ? S->0A
? ? ? ? S->0
? ? ? ? S->A0
? ? ? ? S->0A0
? ? 這時(shí)，G屬于3型文法嗎？
? ? ? ? 答案：不屬于3型文法。S->0A0 既不屬于右線性，也不屬于左線性
如何判斷一個(gè)串是否為某個(gè)文法的句型
? ? 兩種判斷方法：構(gòu)造推導(dǎo)樹和直接進(jìn)行推導(dǎo)。
? ? 例題：
? ? ? ? 已知文法G[S]:S->A0|B1，A->S1|1，B->S0|0;該文法屬于喬姆斯基定義的___文法，它不能產(chǎn)生的串___;
? ? ? ? (1)A.0型? ? ? ? B.1型? ? ? C.2型? ? ? D.3型
? ? ? ? (2)A.0011? ? ? B.1010? ? ? C.1001? ? ? D.0101
? ? ? ? 分析：
? ? ? ? 此文法的推導(dǎo)式有：
? ? ? ? ? ? S->A0
? ? ? ? ? ? S->B1
? ? ? ? ? ? A->S1
? ? ? ? ? ? A->1
? ? ? ? ? ? B->S0
? ? ? ? ? ? B->0
? ? ? ? 這些推導(dǎo)式完全與：A->α|Bα (左線性）形式相符，所以此文法是3型文法
? ? ? ? S為開始符,所以從S開始推導(dǎo)
? ? ? ? （直接推導(dǎo)）由于：
? ? ? ? S->A0->S10->A010->1010
? ? ? ? S->B1->S01->A001->1001
? ? ? ? S->B1->S01->B101->0101
? ? ? ? 此文法不能產(chǎn)生的串為：0011
構(gòu)造推導(dǎo)樹
