若将有限状态自动机(DFA)识别的0、1符号串看做二进制数,则自动机(27)识别的是能被十进制数3整除的

Question

若将有限状态自动机(DFA)识别的0、1符号串看做二进制数，则自动机(27)识别的是能被十进制数3整除的正整数。

A．

B．

C．

D．

Answer 1

正确答案：C
解析：用3除以任何一个整数，余数可能为0、或为1、或为2。因此，若将该DFA识别的0、1串看做是二进制整数，则有以下结论：①0被3除，余数为0。对于选项B、D，无法通过输入1个“0”字符从q0状态回到q0状态，因此可先排除选项B、D。②设能被3整除的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数仍然为0。若在x之后连接一个1所得的数为y，则y=2x+1；此时，y被3整除的余数将等于1。例如，3能整除3，3的数字序列为“11”。对于选项C，无法通过输入2个“1”字符从q0状态到q1状态后再回到q0状态，因此可先排除选项A。③设被3整除后余数为1的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数为2。若在x之后连接一个1所得的数为y，则y=2x+l，且y被3整除的余数将等于0。④设被3整除后余数为2的二进制数为x。若在x之后连接一个0所得的数为y，则y=2x，且y被3整除的余数为1。若在x之后连接一个1所得的数为y，则y=2x+1，且y被3整除的余数仍等于2。假设被3除后的余数为0用q0表示、余数为1用q1表示、余数为2用q2表示。若将空串的值看做0，则选项C所示的自动机识别的是能被3整除的整数。与该自动机等价的正规式是：(0*(1(01*0)*1)*)*。