首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
51
问题
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
(44)提供了一种结构化方法以便使风险识别的过程系统化、全面化,保证组织能够在一个统一的框架下进行风险识别,目的是提高风险识别的质量和有效性。
在信息系统安全建设中,___________确立全方位的防御体系,一般会告诉用户应有的责任,组织规定的网络访问、服务访问、本地和远地的用户认证、拨入和拨出、磁盘和数据加密、病毒防护措施,以及雇员培训等,并保证所有可能受到攻击的地方都必须以同样安全级别加以保
根据GB/T12504-2008《计算机软件质量保证计划规范》的相关规定,以下评审和检查工作中,___________不是必须进行的。
IDS发现网络接口收到来自特定IP地址的大量无效的非正常生成的数据包,使服务器过于繁忙以至于不能应答请求,IDS会将本次攻击方式定义为()。
在信息系统安全保护中,依据安全策略控制用户对文件、数据库表等客体的访问属于()安全管理。
(2010下架构)在实际的项目开发中,人们总是希望使用自动工具来执行需求变更控制过程。下列描述中,______不是这类工具所具有的功能。
(2011上项管)在Linux、Unix和苹果的MacOS操作系统中,系统集成工程师可使用______来构建用C、C++和Java等语言编写的软件。
(2008下系分)某图书订单处理系统中,“创建新订单”和“更新订单”两个用例都需要检查客户的账号是否正确,为此定义一个通用的用例“核查客户账户”。用例“创建新订单”和“更新订单”与用例“核查客户账户”之间是______。
(2006下系分)用例从用户角度描述系统的行为。用例之间可以存在一定的关系。在“某图书馆管理系统”用例模型中,所有用户使用系统之前必须通过“身份验证”,“身份验证”可以有“密码验证”和“智能卡验证”两种方式,则“身份验证”与“密码验证”和“智能卡验证”之间
(2010上项管)范围控制的目的是监控项目的状态,如“项目的工作范围状态和产品范围状态”,范围控制不涉及______。
随机试题
竹笋在我国主要产于________。
现代企业的会计制度具有国际通用规范的性质。()
A、 B、 C、 D、 C
关于抗疟药下列说法正确的是
以下对有关指标说法正确的是()。
台灯作为一个实体可由市场决定其生产量,这种需求量是()。
《尚书》是中国文学史上第一部记叙文和议论文。()
2019年9月23日,“()——庆祝中华人民共和国成立70周年大型成就展”开幕式在北京展览馆举行。中共中央政治局常委、国务院总理李克强出席开幕式并讲话。
Evidenceofthebenefitsthatvolunteeringcanbringolderpeoplecontinuestorollin."Volunteershaveimprovedphysicalands
Whenyourunyourhandsthroughyourlover’shair,you’reprobablynotthinkingaboutyourplaceinthesocialhierarchy.Givey
最新回复
(
0
)