首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
50
问题
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
访问控制是为了限制访问主体对访问客体的访问权限,从而使计算机系统在合法范围内使用的安全措施。以下关于访问控制的叙述中,(17)是不正确的。
按照软件配置管理的基本指导思想,受控制的对象应是__________(62)。实施软件配置管理包括4个最基本的活动,其中不包括__________(63)。(62)
某项目包含A、B、C三项主要活动,项目经理在成本估算时采用自下而上的方法,分别估算出三项活动的成本分别为13万元、23万元和8万元,同时为了应对未来可能遇到的不确定因素,预留了10万元的管理储备,同时为每个活动预留了2万元的准备金。该项目的总预算为____
___________指在软件维护阶段,为了检测由于代码修改而可能引入的错误所进行的测试活动。
质量控制的方法、技术和工具有很多,其中(1)可以用来分析过程是否稳定、是否发生了异常情况。(2)直观地反映了项目中可能出现的问题与各种潜在原因之间的关系。(2)
对项目的投资效果进行经济评价的方法主要有静态分析法和动态分析法。以下叙述中,不正确的是:()。
项目风险识别是指找出影响项目目标顺利实现的主要风险因素,并识别出这些风险究竟有哪些基本特征、可能会影响到项目的哪些方面等问题。以下关于项目风险识别的叙述中,正确的是:()。
某项目范围基准发生变化,经(62)同意,对需求规格说明书进行变更,则该配置项的状态应从(63)。(62)
(2008上项管)一般说来,变更控制流程的作用不包括______。
随机试题
统一指挥就意味着统一领导。()
512×512形式表示的是
新生儿颌骨骨髓炎的感染来源多为
按照现行规定,可发行公司债券的主体有()。Ⅰ.上交所上市公司Ⅱ.发行境外上市外资股的境内股份有限公司Ⅲ.深交所中小板上市公司Ⅳ.深交所创业板上市公司
某油田2013年12月生产原油20万吨,当月销售19.5万吨,为连续生产原油使用0.5万吨;开采天然气1000万立方米,当月销售900万立方米,待售100万立方米。若原油、天然气的单位不含税售价分别为6000元/吨和2000元/万立方米,则该油田本月应纳资
一般资料:求助者,女性,19岁,大学生。下面是心理咨询师与求助者之间的一段咨询对话。心理咨询师:你好!请问我能为你提供什么帮助吗?求助者:我最近总感到紧张,睡不好觉。心理咨询师:你能谈谈是什么事情让你感到紧张,并出现
对未完成义务教育的未成年犯和被采取强制性教育措施的未成年人应当进行义务教育,所需经费由()予以保障。
在新课程背景下,教育评价的根本目的是()。
Therequirementsforhighschoolgraduationhavejustchangedinmycommunity.Asaresult,allstudentsmust【C1】______sixtyhou
在表中八类指标名称中,2007年2月城市居民消费超过上年同期的有()大项。在2007年1—2月份全国居民食品类消费价格指数中,与上年同期相比,降幅最大和增幅最大的分别是()和()。
最新回复
(
0
)