编译原理
文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（）。A、短语文法B、正则文法C、上下文有关文法D、上下文无关文法
题目
文法分为四种类型，即0型、1型、2型、3型。其中3型文法是（）。
- A、短语文法
- B、正则文法
- C、上下文有关文法
- D、上下文无关文法
相似问题和答案
第1题：
●根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与 (28) 等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价 (29) 。从文法描述语言的能力来说， (30) 最强， (31) 最弱，由4类文法的定义可知： (32) 必是2型文法。
(28) A．线性有限自动机
B．非确定的下推自动机
C．图灵机
D．有限自动机
(29) A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
(30) A．1型文法
B．2型文法
C．3型文法
D．0型文法
(31) A．3型文法
B．2型文法
C．0型文法
D．1型文法
(32) A．1型文法
B．0型文法
C．3型文法
D．2型文法
【解析】乔姆斯基把文法分成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型文法。
第2题：
A.短语文法
B.正则文法
C.上下文有关文法
D.上下文无关文法
第3题：
●为下列文法选择最准确的答案：
文法G[S]属于 (52) ：
S→CD Ab→bA
C→aCABa→aB
C→bCBBb→bB
AD→aDC→ε
BD→bDD→ε
Aa→bD
L(G)={ww｜w∈{a，b｝*}
文法G[P]属于 (53) ：
P→0A｜1B｜0
A→0A｜1B｜0P
B→1B｜1｜0
文法G[I]属于 (54) ：
I → lT
I → l
T → lT
T → dT
T → l
T → d
其中，l表示a～z中的任意一个英文字母，d表示0～9中的任意一个数字。
(52) ～(54) A．1型(上下文有关)文法
B．2型(上下文无关)文法
C．定义标识符的3型(正规)文法
D．0型文法
【解析】本题考查4种文法的定义。需要注意的是，4个文法类的定义是逐渐增加限制的，因此每一种正规文法都是上下文无关的，每一种上下文无关文法都是上下文有关的，而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。
第4题：
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，文法被分为4种类型，即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(1)等价，所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说，(3)最强，(4)最弱，由4类文法的定义可知(5)必是2型文法。
A．确定的有穷自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有穷自动机
E．有穷自动机
第5题：
A.短语文法
B.正则文法
C.上下文有关文法
D.上下文无关文法
第6题：
根据乔姆斯基20世纪50年代建立的形式语言的理论体系，语言的文法被分为四种类型，即：O型(上下文有关文法)、1型(上下文相关文法)、2型(上下文无关文法)和3型(正规文法)。其中2型文法与(66)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(67)。从文法描述语言的能力来说，(68)最强，(69)最弱，由四类文法的定义可知：(70)必是2型文法。
(40)
A．确定的有限自动机
B．图灵机
C．非确定的下推自动机
D．非确定的有限自动机
E．有限自动机
第7题：
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为4种类型，即0型(短语文法)，1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中，2型文法与(28)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个非确定的有限自动机必存在一个与之等价(29)。从文法描述语言的能力来说，(30)最强，(31)最弱，由4类文法的定义可知：(32)必是2型文法。
A．线性有限自动机
B．非确定的下推自动机
C．图灵机
D．有限自动机
第8题：
A. 短语文法
B. 上下文无关文法
C. 上下文有关文法
D. 正规文法
第9题：
已知文法G1＝(VT＝{a,b,d}，VN＝{S，A，B}，S,P)，其中P为： S→dAB A→aA|a B→bB|ε 该文法属于(28)文法。
A．0型
B．上下文有关
C．上下文无关
D．正规
解析：乔姆斯基(Chomsky)把文法分成4种类型，即0型、1型、2型和3型，由此产生的语言分别称为0型、1型、2型和3型语言。这几类文法的差别在于对产生式的形式施加不同的限制，如下表所示。0型文法也称短语文法，1型文法也称上下文有关文法，2型文法也称上下文无关文法，2型文法的识别器模型是下推自动机。3型文法也称线性文法(或称正规文法)，其识别器模型是有限状态自动机。文法G1的所有产生式形式都是A→β，其中A∈VN，β∈V*，且第1条规则S→dAB是非线性的，因此文法G1属于2型文法，又称上下文无关文法。
第10题：
在Chomsky定义的4种形式语言文法中，0型文法又称为(51)文法；1型文法又称为(52)文法；2型语言可由(53)识别。
A．短语结构文法
B．上下文无关文法
C．上下文有关文法
D．正规文法