首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 G,只有当G为(26)时,命题“L(G)是空集、有限集或无限集”才是可判定的,当给出两个不同文法G1和G2,只有当G1,G2都是(27)时命题“L(G1)=L(G2)”才是可判定的。
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 G,只有当G为(26)时,命题“L(G)是空集、有限集或无限集”才是可判定的,当给出两个不同文法G1和G2,只有当G1,G2都是(27)时命题“L(G1)=L(G2)”才是可判定的。
admin
2019-03-04
42
问题
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 G,只有当G为(26)时,命题“L(G)是空集、有限集或无限集”才是可判定的,当给出两个不同文法G1和G2,只有当G1,G2都是(27)时命题“L(G1)=L(G2)”才是可判定的。
选项
A、1型
B、2型
C、3型
D、0型
E、2型或3型
答案
C
解析
用计算机对自然语言进行完全自动处理是一件十分困难的事情。这是因为自然语言歧义性大,用形式化的语法描述起来很困难。为了便于计算机的自动处理,语言的形式化描述便显得十分重要。现有算法语言在形式上都是形式语言。
在文法G[S]中,如果存在S
α,则称α是文法G的一个句型,仅含终结符号的句型是文法G的一个句子。语言L(G)是由文法G产生的所有句子组成的集合,其形式定义为:L(G)={α|S
α且α∈
)。我们称文法G1和文法G2是等价的,如果有 L(G1)=L(G2)。即有可能不同的文法产生相同的语言。
文法G是任意给出的,有可能出现这样的情况:给定某个文法G,V
T
中的终止符所组成的任何字符串都无法识别出它能由G生成,即L(G)是个空集。也可能有某个给定的文法G,其L(G)无限制。由于V
T
的终止符可重复出现,字符串长度无限制,因此不可能用列举终止字符串的方法进行句法分析。
那么,如何判断给定G的乙(G)是无限集、有限集,或是空集呢?我们期望能有一种算法,可直接从G出发,通过有限步运算给出L(G)是空集、有限集或无限集的结论。若存在这样的算法,就是可判定的,否则就不是可判定的。研究中发现可否判定L(G)是空集、有限集或无限集与文法G有关。可以证明,当文法G是2型或3型时,是可判定的。
对两个文法G1与G2是否等价即是否有L(G1)=L(G2),只有当G1和G2都是3型文法时,才是可判定的。
转载请注明原文地址:https://kaotiyun.com/show/UtTZ777K
本试题收录于:
数据库系统工程师上午基础知识考试题库软考中级分类
0
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
某信息系统集成项目包括7个作业(A~G),各作业所需的时间、人数以及各作业之间的衔接关系如图所示(其中虚线表示不消耗资源的虚作业):如果各作业都按最早时间开始,那么正确描述该工程每一天所需人数的图为(66)。
以下关于面向对象的叙述中,(25)是不正确的。
按照软件配置管理的基本指导思想,受控制的对象应是__________(62)。实施软件配置管理包括4个最基本的活动,其中不包括__________(63)。(62)
在1号楼办公的小李希望在本地计算机上通过远程登录的方式访问放置在2号楼的服务器,为此将会使用到TCP/IP协议族中的___________协议。
(2011上项管)在Linux、Unix和苹果的MacOS操作系统中,系统集成工程师可使用______来构建用C、C++和Java等语言编写的软件。
(2007上系分)关于UML中的状态图和活动图的叙述中,______是错误的。
(2005上项管)项目小组建设对于项目的成功很重要,因此,项目经理想考察项目小组工作的技术环境如何,有关信息可以在______中找到。
(2009下架构)面向对象的设计模型包含以______(1)表示的软件体系结构图,以______(2)表示的用例实现图,完整精确的类图,针对复杂对象的状态图和用以描述流程化处理的活动图等。(2)
(2008下项管)在项目管理工作中,项目管理师认识到如果只有领导能力而没有管理能力或只有管理能力而没有领导能力,都可能带来不好的结果。以下这些能力中______最能代表项目管理师的领导才能。
(2012上项管)大型信息技术项目一般在需求不十分清晰的情况下开始,项目分成两个主要阶段:需求定义阶段和需求实现阶段。关于大型信息技术项目的需求管理,______的说法是正确的。
随机试题
司马迁将楚地一分为三,其中西楚指()
男性,25岁,因高位小肠瘘1天入院,入院后经颈内静脉插管滴人肠外营养液,两周后突然出现寒战、高热,无咳嗽、咳痰,腹部无压痛和反跳痛。观察8小时如果仍然有高热,应采取的措施是
A.解毒生肌B.托毒生肌C.消肿生肌D.敛疮生肌E.养血生肌血竭能()
根据WHO龋病诊断标准,下面有一项不能诊断为龋牙周CPI指数只需检查6颗指数牙的年龄应在
以下对财务会计与资产评估之间关系的论述中,正确的是()。
某张音乐合辑中包含9首钢琴曲和若干首小提琴独奏曲,在随机播放时听到的第一首是钢琴曲的可能性为60%,那么钢琴曲的数量比小提琴独奏曲的数量()。
一个人对外界的感受力,决定了他对事物的分析、评判能力。如果他只醉心于自我的世界,或疯狂工作,或自言自语,或在家中玩自闭,外界的一切都不会对他产生影响。也就是说,当他拥有喜怒哀乐时,他永远无法与你分享,因为,他跟你没有共鸣。这段文字说明了:
十三大报告指出我国正处在社会主义的初级阶段,其含义是()
Governmentsarerestrainingbusinesstravelersandtouristswithcumbersomevisarequirementsthatdolittletomaketheircount
A、Sarahmovedtoanewaddressaweekago.B、Sarahmissesherfamilyverymuch.C、TheyshouldpaySarahavisit.D、Theyshoulds
最新回复
(
0
)