●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与 (28) 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说， (30) 最强， (31) 最弱，由4类文法的定义可知： (32) 必是2型文法。线性有限自动机非确定的下推自动机图灵机有限自动机(29)

BADAC
【解析】乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。0型文法也称短语文法，0型文法的能力相当于图灵机(Turing)，或者说任何0型语言都是递归可枚举的。1型文法也称上下文有关方法，其能力相当于线形界限自动机。对非终结符进行替换时不必考虑上下文，并且一般不允许替换成空串ε。2型文法也称上下文无关文法，其能力相当于非确定的下推自动机。3型文法也称右线性文法，由于这种文法等价于正规式，所以也称正规文法。3型文法的能力相当于有限自动机。从文法描述语言的能力来说，0型文法最强，3型文法最弱。 语言的文法可以表示成一个四元组(VT，VN，S，P)。由3型文法的定义：一个文法G式3型文法，如果G是二型文法，并且G的每个产生式A→αB或A→α，其中α∈V*T，A，B∈VN，可知3型文法必是2型文法。