有限状态机

有限状态机（英语：finite-state machine，缩写：FSM）又称有限状态自动机，简称状态机，

是表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型。

有些正则引擎就是使用了它. 我们看个 python 里面的例子:

import re
re.findall(r'[0-9]+', '067p')
>>>
['067']

再来看张图片:

开始把当前状态设置为 1，如果满足转换条件（是 0 到 9 之间的数字),

就把当前状态设置为 2，如果满足转换条件（是 0 到 9 之间的数字),

还是把当前状态设置为 2，最后检查是否在接受状态(这里的接受状态是状态 2)。

用 python 来模拟下上图:

#  (1, '0'):2中1是状态，‘0’是转换条件，2是满足转换条件后转到的状态
edges = {(1, '0'): 2,
         (1, '1'): 2,
         (1, '2'): 2,
         (1, '3'): 2,
         (1, '4'): 2,
         (1, '5'): 2,
         (1, '6'): 2,
         (1, '7'): 2,
         (1, '8'): 2,
         (1, '9'): 2,
         (2, '0'): 2,
         (2, '1'): 2,
         (2, '2'): 2,
         (2, '3'): 2,
         (2, '4'): 2,
         (2, '5'): 2,
         (2, '6'): 2,
         (2, '7'): 2,
         (2, '8'): 2,
         (2, '9'): 2}

# 接受的状态
acception = [2]

def fsmsim(string, current_state, edges, acception, pos=0):
    if pos >= len(string):
        return current_state in acception, string[:pos]
    else:
        letter = string[pos]
        if (current_state, letter) in edges:
            current_state = edges[(current_state, letter)]
            pos += 1
            return fsmsim(string, current_state, edges, acception, pos)
        else:
            return False, string[:pos]


fsmsim('0', 1, edges, acception)
>>>
(True, '0')

fsmsim('06', 1, edges, acception)
>>>
(True, '06')

fsmsim('067', 1, edges, acception)
>>>
(True, '067')

fsmsim('067p', 1, edges, acception)
>>>
(False, '067')