首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
admin
2019-06-12
79
问题
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的有穷自动机必存在一个与之等价的(2)。从文法描述语言的能力来说,(3)最强,(4)最弱,由4类文法的定义可知(5)必是2型文法。
选项
A、0型文法
B、1型文法
C、2型文法
D、3型文法
答案
D
解析
乔姆斯基把文法分成四种类型,即0型、1型、2型和3型。0型文法也称短语文法,其能力相当于图灵(Turing)机,或者说任何0型语法都是递归可枚举的。1型文法也称上下文有关方法,其能力相当于线性有界自动机。2型文法也称上下文无关文法,其能力相当于非确定的下推自动机。3型文法也称为线性文法,由于这种文法等价于正规式,因此也称为正规文法。3型文法的能力相当于有穷自动机。自动机分为确定的自动机和非确定的自动机,一个非确定的自动机一定可以转化为一个与之等价的确定的自动机。0、1、2、3型文法是逐渐增加限制的,因此,0、1、2、3型文法描述语言的能力依次递减。也正因为此,每一种3型文法也一定是2、1、0型文法,每一种2型文法也一定是1、0型文法,每一种1型文法也一定是0型文法。
转载请注明原文地址:https://kaotiyun.com/show/1oCZ777K
本试题收录于:
软件设计师上午基础知识考试题库软考中级分类
0
软件设计师上午基础知识考试
软考中级
相关试题推荐
Cisco路由器操作系统IOS有3种命令模式,其中不包括__________。(2011年上半年试题)
RlPv1不支持CIDR,对于运行RlPv1协议的路由器,不能设置的网络地址是__________。(2010年下半年试题)
采用Kerberos系统进行认证时,可以在报文中加入(44)来防止重放攻击。
下图是一个软件项目的活动图,其中顶点表示项目里程碑,联结顶点的边表示包含的活动,则里程碑(1)在关键路径上,活动FG的松弛时间为(2)。(1)
假如有3块容量是300GB的硬盘做RAID5阵列,则这个RAID5的容量是_____________。
阅读以下说明和C语言函数,应填入(n)处。【说明】在一个分布网络中,资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中,资源会有损耗。例如,天然气的气压会减少,电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】本程序从正文文件text.in中读入一篇英文短文,统计该短文中不同单词及出现次数,并按词典编辑顺序将单词及出现次数输出到正文文件word.out中。程序用一棵有序二叉树存
阅读下列函数说明和C函数,将应填入(n)处。【函数3说明】函数DeleteNode(Bitree*r,inte)的功能是:在树根结点指针为r的二叉查找(排序)树上删除键值为e的结点,若删除成功,则函数返回0,否则函数返回-1。二叉查
利用存在的依赖关系构造一个图书馆的对象模型。张三到图书馆借阅一本书,两个月后,他把这本逾期的书返还给图书馆。画出这个场景的时序图。
若要封装对象,并提供不同的接口时,可采用(33);若要将请求封装成对象,则可采用(34);若要将可互换的行为封装起来,并采用委托的方式来决定使用哪一个,则可采用(35)。
随机试题
全面质量管理的计划阶段(P)中,在制定对策时,应综合考虑的“5W”、“1H”是何含义?
中国古代建筑表现出的显著特点有()
深反射包括
A.患者血压明显升高。查体:血压200/130mmHg,眼底出血渗出、视乳头水肿。实验室报告:肾功能不全B.患者血压明显升高,伴有剧烈头痛、呕吐、抽搐C.患者平日有心悸、胸痛、劳力时气促、起立或运动时眩晕。查体:胸骨左缘第3~4肋间可闻较粗糙的
A、静脉注射剂B、气雾剂C、肠溶片D、直肠栓E、阴道栓有溶液型、乳剂型、混悬型
F公司下设销售部、生产部、行管部等七个部门,企业员工210人。其中,生产部下设二胺车间、二酚车间、公用工程车间和总调度办;二胺车间有硝化工段(混二硝基苯装置)、硝化配套工段、加氢工段、二胺精馏工段。2019年,F公司新建年产2×104t改性型胶粘
根据维纳的两维成败归因理论,下列属于稳定的内在原因的是()。
手机对于()相当于()对于商店
罗马在应用科学尤其是农艺学方面取得了较高的成就,其中《论农业》是研究罗马帝国初期奴隶制经济不可多得的历史文献,《论农业》的作者是()。
下列工程项目风险事件中,(24)属于技术性风险因素。
最新回复
(
0
)