首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
32
问题
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
软件可靠性和可维护性测试评审时,不用考虑的是(14)。
项目组合管理是指为了实现特定的战略业务目标,对一个或多个项目组合进行集中管理,包括识别、排序、授权、管理和控制项目、项目集和其他有关工作。以下关于项目组合管理的叙述中,__________是不正确的。
项目进入到执行阶段后,项目经理、项目组成员为了完成项目范围说明书定义的工作,还需执行的是___________。①实施已批准的预防措施以降低潜在负面结果出现的可能性②管理已分配到项目或阶段中的项目团队成员③为项目选择生命周期模型④监管项目总投入情况
在1号楼办公的小李希望在本地计算机上通过远程登录的方式访问放置在2号楼的服务器,为此将会使用到TCP/IP协议族中的___________协议。
质量控制的方法、技术和工具有很多,其中(1)可以用来分析过程是否稳定、是否发生了异常情况。(2)直观地反映了项目中可能出现的问题与各种潜在原因之间的关系。(1)
中间件可以分为数据库访问中间件、远程过程调用中间件、面向消息中间件、事务中间件、分布式对象中间件等多种类型。Windows平台的ODBC和Java平台的JDBC属于()。
(2006下项管)RSA是一种公开密钥算法,所谓公开密钥是指______。
(2005下项管)为了保障数据的存储和传输安全,需要对一些重要数据进行加密。由于对称密码算法______(1),所以特别适合对大量的数据进行加密。国际数据加密算法IDEA的密钥长度是______(2)位。(1)
(2011上网工)下列选项中,同属于报文摘要算法的是______。
随机试题
下列文学常识表述正确的是()。
中外合作经营企业的中方合作者不可以是
我国法律规定,复核死刑案件的合议庭的组成是
根据我国《招标投标法》的规定,招标的方式包括()。
均质杆AB长为l,重W,受到如图所示的约束,绳索ED处于铅垂位置,A、B两处为光滑接触,杆的倾角为α,又CD=l/4,则A、B两处对杆作用的约束力关系为()。
移动模架逐孔施工桥梁上部结构,其主要特点为()。[2013年真题]
根据地质、地形条件,平原河流上的()宜建在封堵汊道的中、下段,并与主流向正交。
会计工作交接完毕后,必须在移交清单上签字或盖章的人有()。
人们以一定方式的共同活动为基础而结合起来的联合体是()
在ASCII代码表中每一个大写字母比它相应的小写字母的ASCII码()。
最新回复
(
0
)