什么是0型文法，1型文法，2型文法，3型文法？

乔姆斯基把方法分成四种类型，即0型、1型、2型和3型。这几种文法类型的概念一定要掌握，是一个非常重要的考点。对于这几种文法，一般书上都只有简单的概念介绍，比较抽象，所以很多学员都没有真正理解。下面我将把概念结合例题进行讲解。

0型文法

设G=（VN，VT，P，S），如果它的每个产生式α→β是这样一种结构：α∈(VN∪VT)*且至少含有一个非终结符，而β∈(VN∪VT)*，则G是一个0型文法。0型文法也称短语文法。一个非常重要的理论结果是：0型文法的能力相当于图灵机(Turing)。或者说，任何0型文语言都是递归可枚举的，反之，递归可枚举集必定是一个0型语言。0型文法是这几类文法中，限制最少的一个，所以我们在试题中见到的,至少是0型文法。

1型文法

1型文法也叫上下文有关文法，此文法对应于线性有界自动机。它是在0型文法的基础上每一个α→β,都有|β|>=|α|。这里的|β|表示的是β的长度。

注意：虽然要求|β|>=|α|，但有一特例：α→ε也满足1型文法。

如有A->Ba则|β|=2,|α|=1符合1型文法要求。反之,如aA->a，则不符合1型文法。

2型文法

2型文法也叫上下文无关文法，它对应于下推自动机。2型文法是在1型文法的基础上,再满足：每一个α→β都有α是非终结符。如A->Ba,符合2型文法要求。

如Ab->Bab虽然符合1型文法要求,但不符合2型文法要求，因为其α=Ab，而Ab不是一个非终结符。

3型文法

3型文法也叫正规文法，它对应于有限状态自动机。它是在2型文法的基础上满足:A→α|αB（右线性）或A→α|Bα（左线性）。

如有：A->a,A->aB,B->a,B->cB，则符合3型文法的要求。但如果推导为:A->ab,A->aB,B->a,B->cB或推导为:A->a,A->Ba,B->a,B->cB则不符合3型方法的要求了。具体的说，例子A->ab,A->aB,B->a,B->cB中的A->ab不符合3型文法的定义,如果把后面的ab,改成“一个非终结符＋一个终结符”的形式（即为aB）就对了。例子A->a,A->Ba,B->a,B->cB中如果把B->cB改为B->Bc的形式就对了,因为A→α|αB（右线性）和A→α|Bα（左线性）两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。

注意：上面例子中的大写字母表示的是非终结符,而小写字母表示的是终结符。

考试的时候不会很难的，一般就是简单的自动机，或者判断给定文法属于哪个类型的文法。
四种文法从上到下是包含关系，注意下一级同上一级的差别，倒着推一下就行了。

至于文法有什么用？好像还真涉及的不多……
编译原理里面词法分析会用到3型文法，语法分析会用到上下文无关文法。
因为程序语言都很简单
只有真实的语言才会用到上下文相关文法吧~~

我一直也很疑惑，0型文法是对应图灵机所能接受的所有的语言
但是后面3种文法为什么是这些限制应该有什么原因吧？期待大牛解答……

一开始猜测1型文法是能判定停机的所有语言？不过仔细想想好像也不是……

3 型文法 对应我们常见的正则表达式，译成“正则文法”比“正规文法”要好一点。
正则表达式用一行非递归规则就能写出来，不能递归引用自己，不能表达嵌套结构。（不过 PERL 的正则表达式比较强大，是接近 2 型文法的存在）

lex 或者 StringTokenizer 都可以对应到一个 3 型文法的产生规则。

2 型文法 （上下文无关文法）很容易被误会成“没有上下文”。它的“上下文无关”指的是每个产生式规则的展开都和上下文无关，但是不能说它没有上下文。

它的一个重要特点是“括号嵌套”，只要括号的开始和终结符都在同一条规则中，它产生的字符串的括号就是嵌套的。譬如它可以产生一族包含 [] 和 () 正确嵌套的字符串：
{"(a[(b)]c)", "(a)[b]", ...}

1 型文法 （上下文有关文法）的括号是可以违背嵌套规则的。譬如它可以产生一族开括号和闭括号数目相等，但不一定正确嵌套的字符串：
{"(a([b)]c)", "(a[)b]", ...}

---------------------------------------------------------------

事实上，语法书里展开规则基本都是上下文无关的，人类语言结构绝大部分都能表示为上下文无关文法。

譬如 wiki 的例子：
(John, (whose (blue car) (was (in the garage)), (walked to the (green store)).

只有极其少数的句子是上下文相关文法的，而且看起来也会有点怪：
[ John saw a (blue car in an ad yesterday] with bright yellow headlights).

 

---------------------------------------------------------------

 

0 1 2 3 型都是停机可判定的 …… 因为 “递归可枚举” 的意思就是存在一个图灵机，它可以将一个文法规则能辨认的所有的字符串从短到长，一个一个不带重复的举出来。那么可以构造另一个图灵机，它一个个枚举可辨认的字符串和输入相比较，如果匹配就返回成功，如果枚举字符串长度大于输入就返回失败，总会停机的 —— 故停机可判定。

 

0 型文法就是图灵机停机可判定的边界，0 型文法再往上的才是停机不可判定的。

 

---------------------------------------------------------------

 

补充： 一般来说一个计算机语言的语法是停机可判定的，即你写出来的程序要么编译成功，要么语法错误。（运行时停机问题是不可判定的，不讨论）。但是 Perl 5 的语法是停机不可判定 的，写成编译器的话，不管怎么修改编译器，都存在一个源文件，让编译器无法判断它是否存在语法错误 ……

额……有些概念没弄的很清楚……

在wiki上看到一个表格：
自动机理论: 形式语言和形式文法
乔姆斯基层级 文法 语言 极小自动机
类型 0         无限制 递归可枚举 图灵机
n/a       (无公用名) 递归 判定器
类型 1       上下文有关 上下文有关 线性有界
n/a        附标 附标 嵌套堆栈
n/a        树-邻接 适度上下文有关 嵌入下推
类型 2       上下文无关 上下文无关 非确定下推
n/a   确定上下文无关 确定上下文无关 确定下推
类型 3         正则 正则 有限

看了一些资料，文法貌似有很多种
从这个表格看来乔姆斯基谱系不是一个严格的类型划分，因为各种类型之间还能插进去别的文法。
他这个类型的划分除了包含关系就没有别的什么更深层原因了？
是不是就是随便分的，或者是从实际应用中总结出来的？
不知道上面的表格是不是列全了？还能不能再插进去别的文法？

花这么多时间去过软设。。。。浪费青春

这些大学的编译原理都快全部还给老师了

呵呵，不要打击楼主mm
软件设计师还是有点技术含量的，考的不是很深，但是覆盖面够广
不知道现在怎么样，当年能考过的还是比较少的

我当年考的时候，一开始复习，看论坛上都说编译原理这块最好放弃
等复习最后确实有时间的时候再临时看一下
所以我就是考试前一天晚上，用了两个小时找了本书看了一下，没想到第二天的题目竟然都做出来了

后来也是基本忘的差不多了
现在是因为工作需要，所以又开始看……

楼主精神可嘉，中国就少这种对基础认真学习的，以至于至今没有自己的操作系统和编程语言。

to 楼上
不是没人做，是因为已经有了，没有必要做了
而且主要是国内重效率，多于质量。

更更重要的是os不是一个人能做出来的，要不微软咋吃饭啊

unix最初也是个内核是一个人做的

现在的话搞os感觉哪怕能优化linux的一个小部分就已经很了不起了

不大习惯0,1,2,3的提法,大致说一下

所谓的3型,即Finite Automata,不需要记忆任何状态，只根据输入进行状态转移。

2型则对应Pushdown Automata，唯一依靠的记忆是栈。

1型的数学意义多于实际意义

回到你提到的限制原因，FSM的实现可以不依赖任何存储设备，只要用硬件搭建好状态就可以，所有这样能够解决的问题，自然需要一个集合来描述，即正则语言。而同样，增加一个栈可以解决的问题的语言，可以用CFG来描述。再复杂的才是图灵机的现实模拟。当然复杂的可以用来模拟简单的，程序设计语言里的正则支持你可以理解为一个帮助你建立简单模型的支持，而不是倒为本末，困惑为什么有了更高级的我们还需要功能更弱的。