首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
65
问题
一个命题的可判定性是指:存在一种算法能给出该命题成立与否的结论。给定文法 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
数据库系统工程师上午基础知识考试
软考中级
相关试题推荐
制定合理的实施进度计划、设计合理的组织结构、选择经验丰富的管理人员、建立良好的协作关系、制定合适的培训计划等内容属于信息系统集成项目的可行性研究中(39)研究的内容。
综合布线系统中用于连接两幢建筑物的子系统是(24)。
职业道德是所有从业人员在职业活动中应该遵循的行为准则,涵盖了从业人员与服务对象、职业与职工、职业与职业之间的关系。以下违背信息系统项目管理师职业道德规范要求的是(5)。
已知网络图各段路线所需费用如下图所示,图中甲线和乙线上的数字分别代表相应点的有关费用。从甲线到乙线的最小费用路线有___________(66)条,最小费用为___________(67)。(67)
根据GB/T12504-2008《计算机软件质量保证计划规范》的相关规定,以下评审和检查工作中,___________不是必须进行的。
下图是一个选择出行路线的“决策树图”,统计路线1和路线2堵车和不堵车的用时和其发生的概率(P),计算出路线1和路线2的加权平均用时,根据计算结果选择出行路线。以下结论中,正确的是:()。
某项目范围基准发生变化,经(62)同意,对需求规格说明书进行变更,则该配置项的状态应从(63)。(63)
(2008上项管)测试是信息系统工程质量监理的重要手段之一,这是由信息系统工程的特点所决定,测试结果是判断信息系统工程质量最直接的依据之一。在整个质量控制过程中,可能存在承建单位、监理单位、建设单位以及专业的测试机构对工程的测试。各方的职责和工作重点有所不
(2013下项管)(2007下监理)当出现招标文件中的某项规定与招标人对投标人质疑问题的书面解答不一致时,应以______为准。
(2008下项管)在项目管理工作中,项目管理师认识到如果只有领导能力而没有管理能力或只有管理能力而没有领导能力,都可能带来不好的结果。以下这些能力中______最能代表项目管理师的领导才能。
随机试题
调节ADH释放最敏感的感受器是
男,30岁,咳嗽3个月,偶有咳痰带血,乏力,体重下降,无发热。查体:双侧颈淋巴结蚕豆大,稍硬,无触痛,右上肺少许湿啰音,最可能的诊断是
A.相加作用B.协同作用C.独立作用D.拮抗作用E.综合作用一种化学物质能减弱另一种化学物质的毒性称为
1999年WHO/ISH高血压指南对1级高血压的诊断标准是
对于实施卫生注册管理的商品,检验检疫机构( )。
张某系中国公民,就职于中国境内甲公司,2014年7月从境内取得如下收入:(1)工资收入3800元,奖金收入600元,岗位津贴300元,交通补贴900元。(2)3年期银行存款利息总收入800元。二级市场股票买卖所得2000元。(3)为乙单位授课收入30
下列行业的企业于2015年1月1日后新购进的固定资产,可缩短折旧年限或采取加速折旧的方法的有()。
Itishardtotrackthebluewhale,theocean’slargestcreature,whichhasalmostbeenkilledoffbycommercialwhalingandis
(1)Iremembermeetinghimoneeveningwithhispushcart.Ihadmanagedtosellallmypapersandwascominghomeinthesnow.It
Unlesshe(tell)______uswhoheis,wewon’tlethimin.
最新回复
(
0
)