登机门|登机门CS 2008 |问题9

以下哪项是可以决定的？

I. Whether the intersection of two regular languages is infinite
II. Whether a given context-free language is regular
III. Whether two push-down automata accept the same language
IV. Whether a given grammar is context-free

（A） 一和二 （B） I和IV （C） 二、三 （D） 二、四 答复: （B） 说明： （A） 两种正则语言的交集是正则的，检查一种正则语言是否无限是可判定的。

（B） 判断上下文无关语言的规律性是不可判定的。 我们检查L（CFG）是否包含长度在n到2n之间的字符串−1，其中n是泵送引理常数。如果是的话，L（CFG）是无限的，否则它是有限的。

（C） 等式问题对于所有语言都是不可判定的，除了有限自动机的情况，即正则语言。

（D） 我们必须检查语法是否符合CFG的规则。如果它遵守这些规则，那么它是可以决定的。

因此，选项（B）是正确的。

如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验