根据乔姆斯基于20世纪50年代建立的形式语言的理论体系，语言的文法被分为　4种类型，即0型(短语文法)，1型(上下有关文法)、2型(上F文无关文法)和3型(正规文法)。其中，2型文法与(56)等价，所以有足够的能力描述多数现今程序设计的语言的句法结构。一个

admin2009-02-15 79

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

选项 A、确定的有限自动机
B、图灵机
C、非确定的下推自动机
D、非确定的有限自动机
E、有限自动机　

答案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→α，其中O∈V*T，A，B∈VN，可知3型文法必是2型文法。

转载请注明原文地址:https://kaotiyun.com/show/cJxZ777K

本试题收录于：软件设计师上午基础知识考试题库软考中级分类

软件设计师上午基础知识考试

软考中级

相关试题推荐

随机试题

最新回复(0)

软件设计师上午基础知识考试

软考中级

文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，那么三级索引时可寻址的文件最大长度为(3)。

SDLCwasinventedbyIBMtoreplacetheolderBisynchronousprotocolforwideareaconnectionsbetweenIBMequipment.Avarietio

Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust

阅读以下有关网络设计的叙述，分析网络结构，回答下面问题。某公司从20世纪70年代中期开始使用PC机，曾使用NOVELL网络，现在要着手组建企业网络。经过需求分析和论证，设计出如下网络方案。

按照消费者对某种产品的使用率，可以将消费者划分为()

下列关于神经系统基本概念的叙述，正确的是()

最大摄氧量数值的表示方法为

上海证券交易所规定的申购、赎回清单应包括(　　)。

下列行为中，属于“必经复议”的受案范围是(　　)。

畲民自称“山哈”，意为山里的客人，其崇拜祖先，重视祭祖。()

下列属于《学记》中提出的教学原则有()。

金融界对1988年《巴塞尔协议》中关于银行资本充足率要求的主要批评意见是()。(中央财经大学)

设R3中两个基α1=[1，1，0]T，α2=[0，1，1]T，α3=[1，0，1]T，β1=[1，0，0]T，β2=[1，1，0]T，β3=[1，1，1]T．已知ξ在基β1，β2，β3下的坐标为[1，0，2]T，求考在基α1，α2，α3下的坐标．

Mostofuswhoworkinearlychildhoodeducationfeelstronglythattheworkwedoisvaluable,【C1】______essential,tothewell

软件设计师上午基础知识考试

软考中级

文件系统采用多重索引结构搜索文件内容。设块长为512字节，每个块号长3字节，如果不考虑逻辑块号在物理块中所占的位置，那么三级索引时可寻址的文件最大长度为(3)。

SDLCwasinventedbyIBMtoreplacetheolderBisynchronousprotocolforwideareaconnectionsbetweenIBMequipment.Avarietio

Networkscanbeinterconnectedbydifferentdevices.Inthephysicallayer,networkscanbeconnectedby(66)orHubs,whichjust

阅读以下有关网络设计的叙述，分析网络结构，回答下面问题。某公司从20世纪70年代中期开始使用PC机，曾使用NOVELL网络，现在要着手组建企业网络。经过需求分析和论证，设计出如下网络方案。

按照消费者对某种产品的使用率，可以将消费者划分为()

下列关于神经系统基本概念的叙述，正确的是()

最大摄氧量数值的表示方法为

上海证券交易所规定的申购、赎回清单应包括( )。

下列行为中，属于“必经复议”的受案范围是( )。

畲民自称“山哈”，意为山里的客人，其崇拜祖先，重视祭祖。()

下列属于《学记》中提出的教学原则有()。

金融界对1988年《巴塞尔协议》中关于银行资本充足率要求的主要批评意见是()。(中央财经大学)

设R3中两个基α1=[1，1，0]T，α2=[0，1，1]T，α3=[1，0，1]T，β1=[1，0，0]T，β2=[1，1，0]T，β3=[1，1，1]T．已知ξ在基β1，β2，β3下的坐标为[1，0，2]T，求考在基α1，α2，α3下的坐标．

Mostofuswhoworkinearlychildhoodeducationfeelstronglythattheworkwedoisvaluable,【C1】______essential,tothewell

上海证券交易所规定的申购、赎回清单应包括(　　)。

下列行为中，属于“必经复议”的受案范围是(　　)。