首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
根据乔姆斯基于20世纪50年代建立的形式语言的理论体系,文法被分为4种类型,即0型(短语文法)、1型(上下文有关文法)、2型(上下文无关文法)和3型(正规文法)。其中,2型文法与(1)等价,所以有足够的能力描述多数现今程序设计的语言的语法结构。一个非确定的
admin
2019-06-12
68
问题
根据乔姆斯基于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
软件设计师上午基础知识考试
软考中级
相关试题推荐
在ISO OSI/RM中,(18)实现数据压缩功能。
在距离矢量路由协议中,每一个路由器接收的路由信息来源于__________。(2012年下半年试题)
下列语句中准确地描述了ISDN接口类型的是(22)。
以下关于网络工程需求分析的叙述中,错误的是()。
在某台PC上运行ipconfig/all命令后得到以下结果,下列说法中错误的是__________。(2010年下半年试题)
在Linux中,________________命令可将文件按修改时间顺序显示。
计算机采用分级存储体系的主要目的是为了解决()的问题。
阅读下列函数说明、图和C代码,将应填入(n)处的字句写在对应栏内。【说明】假定用一个整型数组表示一个长整数,数组的每个元素存储长整数的一位数字,则实际的长整数m表示为:m=a[k]×10k-2+a[k-1]×10k-3+…+a[3]
阅读下列说明和图,回答问题1到问题3。[说明]目前大多数操作系统都采用虚拟存储技术,这样可在较小的可用内存中执行较大的用户程序,可在内存中容纳更多程序并发执行。引入虚拟存储技术,其基本思想是利用大容量的外存来扩充内存,产生一个
一个CRT字符显示器,每帧可显示80字、25行,每个字符点阵为7×9,即横向 7个点,纵向9个点,且字间间隔为1个点,行间间隔为5个点。显示存储器的容量至少为(8)。
随机试题
在Word2010主窗口中,可通过“拆分”命令在一个窗口中显示并编辑同一个义档的不同部分。
下列磷脂中,哪一种含有胆碱?
以下关于鉴定的说法正确的有()
下列哪些类别的公共企业事业单位在提供社会公共服务过程中制作、获取的信息的公开,应依照相关法律、法规和国务院有关主管部门或者机构的规定执行?()
扩大单价法编制单位工程概算以()为依据。
A.颈横动脉、静脉的浅面B.肩胛舌骨肌中间腱以上的颈内静脉周围C.肩胛舌骨肌中间腱以下的颈内静脉周围D.右前斜角肌内侧缘E.二腹肌后腹与面总静脉汇入颈内静脉处右淋巴导管位于()。
2016年7月以来,中央陆续派出环保督察组进驻各地进行现场督察,掀起了一场新治污问责风暴,环保督察,从环保部门牵头到中央主导从以查企业为主转变为“查督并举,以督政为主”,这是我国环境监管模式的重大变革和完善生态文明制度体系的重要举措。建立环保督察工作机制有
A、自然连接B、交C、投影D、并A关系R和关系S有公共域,关系T是通过公共域的等值进行连接的结果,符合自然连接,选A。
IP地址用几个字节表示?
ThetraditionofchristeningandcommissioningashipdatesbacktoancienttimeswhentheGreeks,Romans,EgyptiansandVikings
最新回复
(
0
)