若将有限状态自动机(DFA)识别的0、1符号串看作二进制数,则(6)识别的是能被十进制数3整除的正整数,(7)是与该自动机等价的正规式。

admin2007-10-11  36

问题 若将有限状态自动机(DFA)识别的0、1符号串看作二进制数,则(6)识别的是能被十进制数3整除的正整数,(7)是与该自动机等价的正规式。

选项 A、
B、
C、
D、

答案A

解析 任何一个整数被3除后,余数或为0、或为1、或为2。因此,若将该DFA识别的0、 1串看作是二进制整数,则有以下结论:
   ▲  0被3除,余数为0。
   ▲  设能被3整除的二进制数为x。若在x之后连接一个0所得的数为y,则y=2x,且y被3整除的余数仍然为0。若在x之后连接一个1所得的数为y,则y=2x+1,因此, y被3整除的余数将等于1。
   ▲  设被3整除后余数为1的二进制数为x。若在x之后连接一个0所得的数为y,则y=2x,且y被3整除的余数为2。若在x之后连接一个1所得的数为y,则y2x+l,且y被3整除的余数将等于0。    ‘
   ▲  设被3整除后余数为2的二进制数为x。若在x之后连接一个0所得的数为y,则y=2x,且y被3整除的余数为1。若在x之后连接一个1所得的数为y,则y=2x+l,且y被3整除的余数仍等于2。
   综上,设被3除后的余数为0用qo(下标)表示、余数为1用q1(下标)表示、余数为2用q2(下标)表示,若将空串的值看作0,则下图所示的自动机识别的是能被3整除的整数,其正规式为(0* (1(01*0)*1)*)*。
   
   若限定该自动机识别的0、1序列不能为空串,则相应自动机的状态转换图如下图所示。
   
转载请注明原文地址:https://kaotiyun.com/show/MOQZ777K
0

最新回复(0)