首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为 4种类型,即0型(短语文法),1型(上下有关文法)、2型(上F文无关文法)和3型(正规文法)。其中,2型文法与(56)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为 4种类型,即0型(短语文法),1型(上下有关文法)、2型(上F文无关文法)和3型(正规文法)。其中,2型文法与(56)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个
admin
2009-02-15
31
问题
根据乔姆斯基于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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在内部排序中,通常要对被排序数据序列进行多趟扫描。各种排序方法有其不同的排序实施过程和(时间)复杂性。对给定的整数序列(541,132,984,746,518,181,946,314,205,827)进行从小到大的排序时,采用冒泡排序的第一趟扫描结果是(6
为避免信号在门限附近波动时产生许多报警而加重网络负载,RMON引入了(34)的警报规则。
利用VLAN技术可以把物理上连接的网络从逻辑上划分为多个不同的虚拟子网,可以对各个子网实施不同的管理策略。以下是某台交换机(Switch)的部分配置过程,其中空缺处的命令/参数可能是(48)。Switch#vlandatabaseSwi
TCP协议通过建立连接为用户提供可靠传输,与数据链路层的连接建立不同, TCP要经过(11)才能确定一个连接,这是因为(12)。TCP采用的差错控制也是超时重发技术,超时时间的设置采用(13)策略,以便适应互联网的特性。超时时间设置的根据是(14)。TCP
题1:网络协议是计算机网络和分布系统中互相通信的(21)间交换信息时必须遵守的规则的集合。协议的关键成分中(22)是数据和控制信息的结构或格式;(23)是用于协调和进行差错处理的控制信息;定时是对事件实现顺序的详细说明,而网络体系结构则是(24)。
多路复用技术能够提高传输系统利用率。常用的多路复用技术有(36)。将一条物理信道分成若干时间片,轮换地给多个信号使用,实现一条物理信道传输多个数字信号,这是(37)。将物理信道的总频带宽分割成若干个子信道,每个信道传输一路信号,这是(38)。在光纤中采用的
TheSimpleNetworkManagementProtocol(SNMP)isan(71)protocolthatfacilitatestheexchangeofmanagementinformationbetween(7
在图8-7所示的网络拓扑结构的分支机构路由器上,正确的拨号映射配置语句是(53)。
10个9.6kb/s的信道按时分多路复用在一条线路上传输,如果忽略控制开销,在同步TDM情况下,复用线路的带宽应该是________;在统计TDM情况下,假定每个子信道具有30%的时间忙,复用线路的控制开销为10%,那么复用线路的带宽应该是________
随机试题
中国共产党人第一篇反对教条主义的重要文献是()
下列各项,关于慢性肾功能不全的饮食治疗错误的是()
动态分析方法是指在项目决策分析与评价时考虑资金的(),用复利计算方法计算,从而进行价值判断的一种方法。
下列材料中,在凝结硬化时产生微膨胀的是()。
(操作员:王出纳;账套:205账套;操作日期:2014年1月31日)将收款凭证的第0003号凭证取消出纳签字。
人类行为的变革可以分为下列哪几个阶段()。
对业主具有约束力的业主大会或者业主委员会的决定,必须是()。
一直以来,世界音乐界认为中国没有多声部和声艺术,复调音乐仅存于西方。20世纪50年代,侗族大歌被中国著名音乐家郑律成偶然发现。1986年贵州侗歌合唱团赴法国演出时引起轰动,音乐界惊叹这是中国音乐史上的重大发现,从此改变了中国没有复调音乐的说法。侗族大歌“众
下列关于吉林省气候特征的表述,错误的是:()
在局域网的实际应用中,最重要的是______。
最新回复
(
0
)