首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
admin
2019-06-12
62
问题
根据乔姆斯基于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
软件设计师上午基础知识考试
软考中级
相关试题推荐
以太网帧格式如下图所示,其中“填充”字段的作用是__________。(2011年上半年试题)
下列千兆以太网标准中,传输距离最长的是()。
在UNIX操作系统中,若用户键入的命令参数的个数为1时,执行cat$l命令;若用户键入的命令参数的个数为2时,执行cat>>$2<$1命令。请将下面所示的Shell程序的空缺部分补齐。Case(25)in1)cat$1;;
下列算法中,不属于公开密钥加密算法的是()。
地址192.168.37.192/25是(1),地址172.17.17.255/23是(2)。(1)
X、Y为逻辑变量,与逻辑表达式X+XY等价的是____________。
两个主机通过电缆直接相连,主机A的IP地址为220.17.33.24/28,而主机B的IP地址为220.17.33.100/28,两个主机互相ping不通,这时应该__________。(2013年上半年试题)
假如有3块容量是300GB的硬盘做RAID5阵列,则这个RAID5的容量是_____________。
根据说明中的描述,使用表3-1给出的类的名称,给出图3-1中的A~F所对应的类。根据图3-2所示的播放器行为UML状态图,给出从“关闭”状态到“播放”状态所经过的最短事件序列(假设电池一开始就是有电的)。
阅读下列C程序和程序说明,将应填入(n)处的字句写在对应栏内。【说明】设某城市有n个车站,并有m条公交线路连接这些车站,设这些公交车都是单向的,这n个车站被顺序编号为0至n-1。本程序,输入该城市的公交线路数、车站个数,以及各公交线路上的各站编号,
随机试题
(2013年4月)1947年正式提出“打倒蒋介石,解放全中国”的行动口号是在________发表的宣言。
简述投保人的概念及其应具备的条件。
初治肺结核的描述哪项是正确的
人造木板用于吊顶工程时必须复验的项目是:[2010年第61题]
某啤酒生产线扩建项目,位于原厂区西面100m的空地上,某国道从厂区北侧通过,距公路500m,距火车站26km,当地地形以山地高原为主,平原、绿洲、荒漠东西展开,南北更替,地势由西南向东北渐趋倾斜,当地地表水比较发达,地下水资源丰富。自然土壤由高山寒漠土、高
社区工作的具体目标有( )。
给定资料1.2014年3月5日,李克强总理在政府工作报告中指出,2014年将进一步推进教育发展和改革,使贫困地区农村学生上重点高校人数再增长10%以上,让更多农家子弟有升学机会。扶持农村教育始终是政府工作的重点。根据报告,2013年我国
下列哪一诗句描述的节日与其他三句不同?
2012年新修改的民事诉讼法增加了对公益诉讼制度的规定,这是环境公益诉讼在程序法方面的进步,但仍然缺少具体规定来________。而在司法实践中,由于相关法律条文的缺失,导致法院不受理环保诉讼的情况________。
A.牙龈切除术B.牙周翻瓣术C.引导性组织再生术D.截龈术E.牙冠延长术基础治疗后增生的牙龈未消退,应采取的牙周手术为()。
最新回复
(
0
)