Máy Trạng thái Hữu hạn - Finite State Machines

regexp = r'"(:?[^\\]|(:?\\.))*"'

regexp = r'a+1+'

 edges = { 
(1, 'a'): 2,
(2, 'a'): 2,
(2, '1'): 3,
(3, '1'): 3}
accepting = [3]

def fsmSimulator(string, current, edges, accepting):
    if string == "":
        return current in accepting
    else:
        letter = string[0]
        if (current, letter) in edges:
            current = edges[(current, letter)]
            return fsmSimulator(string[1:], current, edges, accepting)
        else:
            return False

> fsmSimulator("aa1", 1, edges, accepting)

Máy trạng thái hữu hạn có 2 loại: máy trạng thái hữu hạn xác định và máy trạng thái hữu hạn không xác định.
Ví dụ ở trên là máy trạng thái hữu hạn xác định. Ví dụ sau nói về máy trạng thái hữu hạn không xác định, cụ thể là ở nhãn "epsilon", cho phép rẽ nhánh từ một nút. (Nhãn epsilon này cũng giải thích cho việc khi đầu vào rỗng '' thì vẫn còn khả năng duyệt FSM được). 

VD:
 regexp = r'ab+c?|a+'
 edges = {
(1, 'a'): [2,3]
(2, 'a'): [2]
(3, 'b'): [4,3]
(4, 'c'): [5]
}
accepting = [2,5]

 def nfsmSimulator(string, current, edges, accepting):
    if string == "":
        return current in accepting
    else:
        letter = string[0]
        if (current, letter) in edges:
            newstates = edges[(current, letter)]
            for newstate in newstates:
                if
nfsmSimulator(string[1:], newstate, edges, accepting)
                return True
        return False