GATE | GATE-CS-2007 |问题29

一个最小状态确定性有限自动机接受语言L={w | wε{0,1}*，w中0和1的个数分别可被3和5整除 （A） 15个州 （B） 11个州 （C） 10个州 （D） 9个州 答复: （A） 说明：

这里，由0和1组成的字符串w应该具有这样的属性：字符串w中的0的个数应该可以被3整除（N（0）%3=0），字符串w中的1的个数应该可以被5整除（N（1）%5=0）。

话虽如此，该语言将包含以下字符串：{ε，000，11111，00011111111，00111101，11111 000，10101011，000000 11111

所以，自动机接受的字符串长度必须是0,3,5,8,11,13,14,16…。以此类推，即长度方程为3x+5y（其中x，y>=0）

模3给出余数为（0，1，2），模5给出余数为（0，1，2，3，4）。因此，3*5个状态，即自动机中将有15个状态来表示这一点。

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