A.1型B.2型C.3型D.0型E.2型或3型

Question

A．1型

B．2型

C．3型

D．0型

E．2型或3型

Answer 1

正确答案：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型文法时，才是可判定的。