上篇講述了文法和語言的概念，什么是文法？相信大家都有所了解了。
本篇講述文法的類型，**某些類型的文法及其產生的語言得到了細致的研究并被偉大的[喬姆斯基](http://www.baidu.com/s?wd=%E4%B9%94%E5%A7%86%E6%96%AF%E5%9F%BA&rsv_spt=1&issp=1&rsv_bp=0&ie=utf-8&tn=baiduhome_pg&rsv_sug3=1&rsv_sug=0&rsv_sug4=842)單獨命名**。喬姆斯基先生能眾多規則中進行進一步歸納，對產生式施加不同的限制。而我們只能學習人家喬姆斯基先生研究好的東東，學習這種思考問題的方式。
四種文法之間的關系是將產生式作進一步的限制而定義的：
<table border="1" cellspacing="1" cellpadding="1" width="726" style="width:726px; height:171px"><tbody><tr><th scope="col"><span style="font-size:14px">文法類型</span></th><th scope="col"><span style="font-size:14px">規則</span></th><th scope="col"><span style="font-size:14px">示例</span></th></tr></tbody><tbody><tr><th scope="row"><span style="font-size:14px">0型文法</span></th><td><span style="font-size:14px">a->b 產生式左邊a至少含有一個非終結符</span></td><td><p><span style="font-size:14px">nA->b</span></p><p><span style="font-size:14px"/>?</p></td></tr><tr><th scope="row"><span style="font-size:14px">1型文法</span></th><td><span style="font-size:14px">在0型基礎上，a->b 產生式右側的長度越來越長。|b| >=|a| S->ε 除外。</span></td><td><p><span style="font-size:14px">nA->bSd</span></p><p>?</p></td></tr><tr><th scope="row"><span style="font-size:14px">2型文法</span></th><td><span style="font-size:14px">在1型基礎上，a->b左側為一個非終結符。</span></td><td><p><span style="font-size:14px">A->bSd</span></p><p>?</p></td></tr><tr><th scope="row"><span style="font-size:14px">3型文法</span></th><td><span style="font-size:14px">在2型基礎上，a->b 右側的形式為：A->cB 或A->c （僅此兩種形式）AB為非終結符</span></td><td><p><span style="font-size:14px">A->bS </span></p><p><span style="font-size:14px">A-n</span></p></td></tr></tbody></table>
從0型文法到3型文法，規則越來越嚴格了。
**0型文法**：可由圖靈機識別（關于[圖靈機](http://baike.baidu.com/view/117065.htm)，百度百科描述很詳細了。）
**1型文法**：上下文有關文法。（任何產生規則的左手端和右手端都可以被終結符和非終結符的上下文所圍繞，喬姆斯基描述自然語言的一種方式介入的，在自然語言中一個單詞是否可以出現在特定的位置要依賴于上下文。）
**2型文法**：上下文無關文法。之所以稱為上下文無關文法，是因為在推導式中a->b ，字符a總可以被字符串b自由替換，而無需考慮字符a出現的上下文。
**3型文法**：正規語言，之所人稱作正規語言（正則語言），可能是因為3型文法只有兩種形式 A->aB A->a ，比較固定，規則明顯，所以稱為正規語言。（小菜這么想的）
本篇就到這里啦，下篇講述上下文無關文法及其語法樹。
愿開心閱讀。(*^__^*)
????????
