2、文法分为四种类型，即0型、1型、2型、3型。其中2型文法是（）A．短语文法B．正则文法C．上下文有关文法D．上下文无关文法

A.0型

B.1型

C.2型

D.3型

此题为判断题(对，错)。

为下列文法选择最准确的答案：

文法G[S]属于(12)：

S→CD Ab→bA

C→aCA Ba→aB

C→bCB Bb→bB

AD→aD C→s

BD→bD D→c

Aa→bD

L(G)={ww|w∈{a,b)*)

文法G[冈属于(13)：

P→0A|1B|O

A→0A|1B|0P

B→1B|1|0

文法G[1]属于(14)：

I→1T

I→1

T→1T

T→dT

T→1

T→d

其中，1表示a～z中的任意一个英文字母，d表示0～9中的任意一个数字。

A．1型(上下文有关)文法

B．2型(上下文无关)文法

C．定义标识符的3型(正规)文法

D．0型文法

一个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定文法 G，只有当G为(26)时，命题“L(G)是空集、有限集或无限集”才是可判定的，当给出两个不同文法G1和G2，只有当G1，G2都是(27)时命题“L(G1)＝L(G2)”才是可判定的。

A．1型

B．2型

C．3型

D．0型

E．2型或3型

有限状态自动机可用5元组(VT，Q，δ，q0，Qf)来描述，它可对应于(28)。设有一有限状态自动机M的定义如下：

VT＝{0，1}，Q＝{q0，q1，q2)

δ定义为：

δ(q0，0)=q1 δ(q1，0)=q2

δ(q2，1)=q2 δ(q2，1)=q2

Qf={q2}。

M是一个(29)有限状态自动机，它所对应的状态转换图为(30)，它所能接受的语言可以用正则表达式表示为(31)，其含义为(32)。

A．0型文法

B．1型文法

C．2型文法

D．3型文法

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

A．线性有限自动机

B．非确定的下推自动机

C．图灵机

D．有限自动机

A.短语文法

B.正则文法

C.上下文有关文法

D.上下文无关文法

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

A．确定的有穷自动机

B．图灵机

C．非确定的下推自动机

D．非确定的有穷自动机

E．有穷自动机

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

A．短语结构文法

B．上下文无关文法

C．上下文有关文法

D．正规文法

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

A．确定的有限自动机

B．图灵机

C．非确定的下推自动机

D．非确定的有限自动机

E．有限自动机