首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为 4种类型,即0型(短语文法),1型(上下有关文法)、2型(上F文无关文法)和3型(正规文法)。其中,2型文法与(56)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,语言的文法被分为 4种类型,即0型(短语文法),1型(上下有关文法)、2型(上F文无关文法)和3型(正规文法)。其中,2型文法与(56)等价,所以有足够的能力描述多数现今程序设计的语言的句法结构。一个
admin
2009-02-15
45
问题
根据乔姆斯基于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
软件设计师上午基础知识考试
软考中级
相关试题推荐
某计算机系统中,16位浮点数的表示格式如图6-1所示。其中阶码4位(含1位符号)为定点整数,尾数12位(含1位符号)为定点小数,设一个数机器码为1110001010000000。若阶码为移码且尾数为原码,则其十进制数真值为(2);若阶码为补码且尾数为补
IETF定义的多协议标记交换(MPLS)是一种第三层交换技术,MPLS网络由标记交换路由器和标记边缘路由器组成,负责为网络流添加/删除标记的是(29)。
CMM模型将软件过程的成熟度分为5个等级。属于4级以上的关键过程域是(14)。
在网络体系结构中,第N层协议利用(24)提供的服务向(25)提供服务。对等实体是指(26)。数据在同一个系统自上层传到下层,这种数据格式称为(27)。IEEE802局域网协议的结构提供对高层的支持,屏蔽了具体的媒体和访问控制方法。为连到局域网上的端系统提供
在实现文件系统时,为加快文件目录的检索速度,可利用“文件控制块分解法”。假设目录文件存放在磁盘上,每个盘块512字节。文件控制块占64字节,其中文件名占8字节,文件内部号和文件其他描述信息占56字节。设某一目录文件共有254个文件控制块,采用分解法前查找该
Linux在安装了Web服务器后;当在inted下启动时,在系统文件etc/services中要添加(30),在单独运行时,命令是(31)。Web系统的系统配置文件(32)定义了服务器在DNS数据库中注册的主机名,这是通过(33)命令定义的。测试WWW服务
在UNIX操作系统中,以下Shell程序实现当用户键入的命令参数的个数为1时,执行cat$1命令;若用户键入的命令参数的个数为2时,执行cat>>$2<$1命令。case(36)in1)cat$1;;2)cat
某企业的网络拓扑结构如图2.2所示,采用VPN来实现网络安全。请简要叙述从企业总部主机到分支机构主机通过IPsec的通信过程。从一下几个方面来对比IPSecVPN和SSLVPN各自的优势。安全通道、认证和权限控管、安全测试、病毒入侵、防火墙
10个9.6kb/s的信道按时分多路复用在一条线路上传输,如果忽略控制开销,在同步TDM情况下,复用线路的带宽应该是________;在统计TDM情况下,假定每个子信道具有30%的时间忙,复用线路的控制开销为10%,那么复用线路的带宽应该是________
计算机在进行浮点数的相加(减)运算之前先进行对阶操作,若x的阶码大于y的阶码,则应将__________。(2008年下半年试题)
随机试题
管式泵的游动阀也称为吸入阀,它除了有阀球、阀座、阀罩外还有打捞头,供油井作业时捞出或便于其他作业等。()
购置新建商品房,其缴纳房产税的时间是()
芍药汤中的反佐药为( )。
区域环境质量评价的内容包括
按定额反映的生产要素消耗内容分类,可以把工程建设定额分为()。
某综合楼工程项目合同价为1750万元,该工程签订的合同为可调值合同。合同报价日期为1999年4月1日。施工单位1999年第4季度完成产值是710万元。工程人工费、材料费构成比例以及相关季度造价指数如表1所示:在施工过程中,发生如下几项事件:
某企业为增值税一般纳税人,2016年6月新建厂房,当月委托另一单位为其建筑设计,取得增值税专用发票上注明价款100万元,并按现行规定抵扣了进项税额,7月因管理不善发生非正常损失,则该企业7月相关账务处理正确的有()。
硬货币是()。
手机对于()相当于()对于保健
A、Becausesheneedstoflyhomeovertheschoolbreak.B、BecauseherroommatewillflytoHawaiitobuynewclothes.C、Becauses
最新回复
(
0
)