首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
admin
2019-06-12
80
问题
根据乔姆斯基于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
软件设计师上午基础知识考试
软考中级
相关试题推荐
以太网采用的CSMA/CD协议,当冲突发生时要通过二进制指数后退算法计算后退时延,关于这个算法,下面的论述中错误的是()。
以下关于VLAN标记的说法中,错误的是_____________。
默认管理VLAN是()。
地址编号从80000H到BFFFFH且按字节编址的内存容量为(1)KB,若用16K×4bit的存储器芯片构成该内存,共需多少(2)片。(2)
某进程有4个页面,页号为0~3,页面变换表及状态位、访问位和修改位的含义如下图所示。系统给该进程分配了3个存储块,当采用第二次机会页面替换算法时,若访问的页面1不在内存,这时应该淘汰的页号为(9)。
IDS设备的主要作用是(42)。
请使用说明中的术语,给出上图中类Customer和类Person的属性。识别关联的多重度是面向对象建模过程中的一个重要步骤。根据说明中给出的描述,完成图中的(1)~(6)。
阅读下列函数说明,将应填入(n)处的字句写在对应栏内。【函数1说明】函数compare(SqListA,SqListB)的功能是:设A=(al,…,am)和B=(b1,…,bn)均为顺序表,“比较”,两个顺序表A和B的大小。设A’和B’
某计算机的虚拟存储系统有40位虚拟地址,32位实际地址,虚页为1M(220)。假设有效位、保护位、修改位和使用位共用去四位,所有虚页都在使用。则页表大小为(20),页面的大小为(21)。
为了(21)目的,通过安装、显示、传输或者存储软件方式使用软件,可以不经软件著作权人许可,不向其支付报酬。
随机试题
先秦时期最能反映儒家思想的一部语录体著作是( )
已知函数y=xlnx,则dy=2xlnx+1dx。()
对于石膏类模型材料,其混水率越大,则
膏淋日久,精微外泄,可致消瘦乏力,气血大亏,最终可形成以下哪种病证
背景某堤防工程项目业主与承包商签订了工程施工承包合同。合同中估算工程量为5300m3,单价为180元/m3。合同工期为6个月。有关付款条款如下:(1)开工前业主应向承包商支付估算合同总价20%的工程预付款;(2)业主自第一个月起,从承包商
患者需吸入的氧气浓度为37%,氧流量应调节为每分钟()。
在小组中,与组员沟通的技巧是营造轻松、安全的氛围,专注与倾听,(),适当帮助梳理,及时进行小结。
简述我国猿人遗址的发现与意义。
ThomasHardy’snovelsaresaidtosufferfromthe"longarmofcoincidence"becausetoomanyeventsseemtohaveacasualrather
Aflashingredlight______motoriststotroubleahead.
最新回复
(
0
)