问题 单项选择题

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

A.A

B.B

C.C

D.D

答案

参考答案: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)*)*。

单项选择题
单项选择题