Chomsky定义的四种形式语言文法中，2型语言可由（)识别。A、短语结构文法B、前后文无关文法C、前后

A.短语结构

B.前后文无关

C.前后文有关

D.正规

A. 短语文法

B. 上下文无关文法

C. 上下文有关文法

D. 正规文法

在Chomsky定义的4种形式语言文法中，0型文法又称为(51)文法；1型文法又称为(52)文法；2型语言可由(53)识别。

A．短语结构文法

B．上下文无关文法

C．上下文有关文法

D．正规文法

程序设计语言包括(41)等几个方面，它的基本成分包括(42)。Chomsky(乔姆斯基)提出了形式语言的分层理论，他定义了四类文法：短语结构文法、上下文有关文法、上下文无关文法和正则文法。一个文法可以用一个四元组G=(∑，V,S，P)表示，其中，∑是终结符的有限字符表，y是非终结符的有限字母表，S(∈V)是开始符号，P是生成式的有限非空集。在短语文法中，P中的生成式都是α→β甲的形式，其中α∈(43)，β∈(∑∪V)*。在上下文有关文法中，户中的生成式都是α1Aα2→α1βα2的形式，其中A∈(44)，β∈(∑∪V*)，β≠。在上下文无关文法中，户中的生成式的左部正(45)。

A．语法、语义

B．语法、语用

C．语义、语用

D．语法、语义、语用

●程序设计语言包括 (41) 等几个方面，它的基本成分包括 (42) 。Chomsky(乔姆斯基)提出了形式语言的分层理论，他定义了四类文法：短语结构文法、上下文有关文法、上下文无关文法和正则文法。一个文法可以用一个四元组G=(∑,V,S,P)表示，其中，∑是终结符的有限字符表，V是非终结符的有限字母表，S(∈V)是开始符号，P是生成式的有限非空集。在短语文法中，P中的生成式都是α→β的形式，其中a∈ (43) ，β∈(∑∪V)*。在上下文有关文法中，P中的生成式都是α1Aα2→α1βα2的形式，其中A∈ (44) ，β∈(∑∪V*),β≠ε。在上下文无关文法中，P中的生成式的左部∈ (45) 。

(41) A．语法、语义

B．语法、语用

C．语义、语用

D．语法、语义、语用

(42) A．数据、传输、运算

B．数据、运算、控制

C．数据、运算、控制、传输

D．顺序、分支、循环

(43)A．V+

B．(∑∪V)

C．(∑∪V)*

D．(∑∪V)*V(∑∪V)*

(44) A．V

B．V+

C．∑∪V

D．(∑∪V)*

(45) A．V

B．V+

C．∑∪V

D．(∑∪V)*

A.短语结构文法

B.前后文无关文法

C.前后文有关文法

D.正规文法

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

(40)

A．确定的有限自动机

B．图灵机

C．非确定的下推自动机

D．非确定的有限自动机

E．有限自动机

A.0型

B.1型

C.2型

D.3型

A.0型语言

B.1型语言

C.2型语言

D.3型语言