首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
61
问题
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
确定适用于项目的质量标准并决定如何满足这些标准是__________过程的主要功能。
软件项目质量保证中的审计指的是__________。
大数据对产品、企业和产业有着深刻的影响。把信息技术看作是辅助或服务性的工具已经成为过时的观念,管理者应该认识到信息技术的广泛影响,以及怎样利用信息技术来创造有力而持久的竞争优势,__________将是未来经济社会发展的一个重要特征。
在建筑物综合布线系统中,由用户终端到信息插座之间的连线系统称为()。
(2007下监理)文件存储设备中,______不支持文件的随机存取。
(2014上项管)某政府公开招标项目,在编制了招标文件并发布了招标公告后,招标人应随即______。
(2007上系分)采用UML分析用户需求时,用例UC1可以出现在用例UC2出现的任何位置,那么UC1和UC2之间的关系是______。
(2009上项管)安全审计是保障计算机系统安全的重要手段之一,其作用不包括______。
(2010上项管)范围控制的目的是监控项目的状态,如“项目的工作范围状态和产品范围状态”,范围控制不涉及______。
(2011上网工)下列选项中,同属于报文摘要算法的是______。
随机试题
切线类技术分析方法中,常见的切线有()。Ⅰ.压力线Ⅱ.支撑线Ⅲ.趋势线Ⅳ.移动平均线
统一战线内的社会主义联盟和爱国主义联盟的关系是()
直径为300mm的蒸汽管道,放在剖面为300mm×400mm的砖砌沟中,管道表面的发射率ε1=0.74,砖砌沟的发射率ε2=0.92,蒸汽管道的表面温度为200℃,砖砌沟的平均温度为80℃,每米蒸汽管道的辐射热损失为()W。
旅游法律关系的构成包括()。
亚里士多德在人类教育史上第一个提出________的论点,为人类研究儿童、教育儿童出了正确方向。
某镇一年内接连发生了数十起盗窃水泵案件,该镇派出所多次组织召开专题案情分析会,对每一个现场进行研判。民警发现该镇的彭某具有重大的作案嫌疑,掌握详实线索后,民警果断出击,在彭某家中将其抓获。派出所民警甲在确定彭某有重大嫌疑后,决定对彭某的住所进行搜查。对
根据下列统计资料回答问题。能够从上述资料中推出的是:
_____是理所当然的家庭教育的鼻祖。
PedestriansOnly1.Theconceptoftraffic-freeshoppingareasgoesbackalongtime.DuringtheMiddleAges,traffic-frees
这个全球第三大个人电脑厂商第一季度在中国市场的占有率为31.3%,较去年第四季的36%有所下降,但仍居中国市场老大位置。
最新回复
(
0
)