大门|大门-CS-2001 |问题50

考虑一个DFA∑ = {a，b}接受a的个数可被6整除，b的个数可被8整除的所有字符串。DFA将拥有的最少州数是多少？ （A） 8. （B） 14 （C） 15 （D） 48 答复: （D） 说明： 我们为可被6整除的字符串构造了一个DFA。 它需要至少6个状态作为字符串长度mod 6=0、1、2、3、4、5 我们为可被8整除的字符串构造了一个DFA。 它至少需要8个状态作为字符串长度mod 8=0、1、2、3、4、5、6、7 如果第一个DFA最小，第二个DFA也最小，那么合并两个DFA后，结果DFA也将最小。这种DFA被称为复合自动机。 因此，结果DFA中的最小状态=6*8=48 因此，选项（D）就是答案。 如果你在上面的帖子中发现任何错误，请在下面发表评论。 这个问题的小测验