初学编译原理——构造一个DFA，它接受字母表∑={0,1}上能被能5整除的二进制数

题目：构造一个DFA，它接受字母表∑={0,1}上能被能5整除的二进制数

解析如下：

注意，我们要明白DFA是一个一个数字扫描的，比如二进制数字101，其先扫描的字符是1，接下来是0，最后是1。
要求能被5整除的二进制数，例如0、101、1010等，一个数除以5，其余数可能为0、1、2、3、4共五个状态，0除以5还是0，因此0既为初态，也为终态。

首先是初态0状态，当扫描的第一个字符为1时，构成了二进制数字1，1除以5的余数还是1，因此到达了1状态，当在0状态扫描到的字符还是0时，说明二进制数字还是0，余数是0，因此回到本身0状态；

接下来是1状态，当扫描的下一个字符为1时，便构成了二进制数字11，即数字3，3除以5的余数还是3，因此到达3状态；如果1状态的下一个字符是0，便构成了二进制数字10，即数字2，同理到达2状态；

从2状态出发，即10，如果下一个字符是1，构成的二进制数字便是101，即十进制数字5，5除以五的余数是0，因此到达了0状态，即终态；如果2状态的下一个字符是0，构成的二进制数字是100，即4，4除以5的余数是4，到达了4状态；

从3状态出发，即11，如果下一个字符是1，构成的二进制数字便是111，即十进制数字7，7除以五的余数是2，因此到达了2状态；如果3状态的下一个字符是0，构成的二进制数字是110，即6，6除以5的余数是1，到达了1状态；

从4状态出发，即100，如果下一个字符是1，构成的二进制数字便是1001，即十进制数字9，9除以五的余数是4，因此到达了4状态；如果4状态的下一个字符是0，构成的二进制数字是1000，即8，16除以5的余数是3，到达了3状态

综上所述，将其构造为DFA便如下图所示，其中，0既为初态，也为终态