2. 计算机
  3. 一个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定文法　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)”才是可判定的。

admin2019-03-04  36
问题 一个命题的可判定性是指：存在一种算法能给出该命题成立与否的结论。给定文法　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，VT中的终止符所组成的任何字符串都无法识别出它能由G生成，即L(G)是个空集。也可能有某个给定的文法G，其L(G)无限制。由于VT的终止符可重复出现，字符串长度无限制，因此不可能用列举终止字符串的方法进行句法分析。
   那么，如何判断给定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

数据库系统工程师上午基础知识考试

软考中级

相关试题推荐
随机试题
最新回复(0)