能力倾向|门CS 1998 |问题10

以下哪些集合可以被确定性有限状态自动机识别？ （A） 数字1，2，4，8，2^n，………。用二进制写的。 （B） 数字1，2，4，…。。，2^n，………。用一元文字写的。 （C） 一组二进制字符串，其中0的数量与1的数量相同。 （D） 集合{1，101，11011，1110111，…} 答复: （A） 说明： 如果有一种无限的语言，而对于这种语言，如果它们不存在任何模式，那么我们可以肯定地说，给定的语言是不规则的，但是如果这种语言存在模式，那么它可能是规则的语言，也可能不是规则的语言，为了确保给定的语言是规则的，如果我们能够为这种语言绘制DFA，那么它肯定是规则的，否则就不是规则的，

因此，选项（A）是常规语言，因为它可以用二进制编写，即：。，

L = {1, 10, 100, 1000, 10000, …} 

正则表达式是（10*），因为对于这个表达式，我们可以绘制DFA。

因此，选项（A）是正确的。 这个问题的小测验