上篇讲述了文法和语言的概念，什么是文法？相信大家都有所了解了。
本篇讲述文法的类型，**某些类型的文法及其产生的语言得到了细致的研究并被伟大的[乔姆斯基](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 ，比较固定，规则明显，所以称为正规语言。（小菜这么想的）
本篇就到这里啦，下篇讲述上下文无关文法及其语法树。
愿开心阅读。(*^__^*)
