A.1型文法B.0型文法C.3型文法D.2型文法

Question

A．1型文法

B．0型文法

C．3型文法

D．2型文法

Answer 1

正确答案：C
解析：乔姆斯基把文法分成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型文法。