Deterministic Finite

Deterministic Finite

@Deterministic Finite-state automata

Question : 设计一个finite-state Automata，语言{0.1}， 二进制形式，可以识别5的倍数

①N mod 5 = {0，1，2，3，4}
一个数除以5的余数只能有0或1或2或3或4，这5种状态，所以自动机也需要5个states
②state q0 代表余数为0（也就是5的倍数，accepted state，also initial state）
state q1 代表余数为1， so forth。。。。
③每个状态必须接受语言0和1，也就是说每个状态都必须通过0，1到达另一个状态
④例如：0对应的十进制为0， 0 mod 5 = 0， 所以q0—0---> q0
01对应的十进制为1， 1 mod 5 = 1， 所以q0—1---> q1
010对应的十进制为2， 2 mod 5 =2，所以q0—1---> q1—0---> q2
011对应的十进制为3， 3 mod 5 =3，所以q0—0--->