有限状态机概述
有限状态机Finite state machine (FSM)，finite-state automaton (FSA),finite automaton是一种计算模型，即设计系统的概念工具。它处理一系列改变系统状态的输入。有限状态机的一个实际例子是电子游戏控制器上的一组按钮，这些按钮是游戏中的一组特定动作。当用户输入并点击某些按钮时，系统知道实现相应的操作。
数学模型
有限状态机数学模型为(Σ,S,s0,δ,F)：
- Σ，alphabet表示有效输入
- S 有限的，非空的一组状态
- s0 初始状态，S的一个元素
- δ，transition表示从一种状态到另一种状态的规则方法
- F是一组有限状态，是S的子集（可能为空）
- O一组输出（可能为空）
以售票机为例：
- Σ (m, t, r) ： 付款m, 出票t, 退款r
- S (1, 2) : 没付款状态, 付款状态
- s0 (1) ：初始状态
- δ (shown below) : transition function: δ : S x Σ → S
- F : empty
- O (p/d) :打印票据p, 退款d
分类
Acceptors
Acceptors(受体，也称为检测器或识别器)产生二进制输出，指示是否接受接收到的输入。接受者的每个状态要么接受（accepting）要么不接受（non accepting）。一旦接收到所有输入，如果当前状态为接受（accepting）状态，则该输入被接受;否则将被拒绝。通常，输入是一个符号(字符)序列；没有动作(actions)。
Transducers
Transducers根据给定的输入与/或使用动作的状态产生输出。应用在控制系统，在控制系统又分为两种：
- Moore machine
只使用actions，即输出只依赖于状态。Moore模型的优点是简化了行为。
- Mooly machine
也使用输入动作，即输出依赖于输入和状态。Mooly模型的使用通常会减少状态的数量。
用Python实现一个有限状态机
class Transition:
"""A change from one state to a next"""
def __init__(self, current_state, state_input, next_state):
self.current_state = current_state
self.state_input = state_input
self.next_state = next_state
def match(self, current_state, state_input):
"""Determines if the state and the input satisfies this transition relation"""
return self.current_state == current_state and self.state_input == state_input
class FSM:
"""A basic model of computation"""
def __init__(
self,
states=[],
alphabet=[],
accepting_states=[],
initial_state=''):
self.states = states
self.alphabet = alphabet
self.accepting_states = accepting_states
self.initial_state = initial_state
self.valid_transitions = False
def add_transitions(self, transitions=[]):
"""Before we use a list of transitions, verify they only apply to our states"""
for transition in transitions:
if transition.current_state not in self.states:
print(
'Invalid transition. {} is not a valid state'.format(
transition.current_state))
return
if transition.next_state not in self.states:
print('Invalid transition. {} is not a valid state'.format)
return
self.transitions = transitions
self.valid_transitions = True
def __accept(self, current_state, state_input):
"""Looks to see if the input for the given state matches a transition rule"""
# If the input is valid in our alphabet
if state_input in self.alphabet:
for rule in self.transitions:
if rule.match(current_state, state_input):
return rule.next_state
print('No transition for state and input')
return None
return None
def accepts(self, sequence):
"""Process an input stream to determine if the FSM will accept it"""
# Check if we have transitions
if not self.valid_transitions:
print('Cannot process sequence without valid transitions')
print('Starting at {}'.format(self.initial_state))
# When an empty sequence provided, we simply check if the initial state
# is an accepted one
if len(sequence) == 0:
return self.initial_state in self.accepting_states
# Let's process the initial state
current_state = self.__accept(self.initial_state, sequence[0])
if current_state is None:
return False
# Continue with the rest of the sequence
for state_input in sequence[1:]:
print('Current state is {}'.format(current_state))
current_state = self.__accept(current_state, state_input)
if current_state is None:
return False
print('Ending state is {}'.format(current_state))
# Check if the state we've transitioned to is an accepting state
return current_state in self.accepting_states
Transition类包含match()函数。一种快速了解有限状态机的当前状态和输入是否允许我们进入下一个定义的状态的方法。
初始化之后，FSM类需要调用add_transitions()方法。此方法验证我们的转换规则是否使用有效状态设置。
然后，我们可以使用带有输入列表的accepts()方法来确定我们的机器是否处于接受状态。
执行程序：
# Set up our FSM with the required info:
# Set of states
states = ['State 1', 'State 2', 'Error']
# Set of allowed inputs
alphabet = [1, 0]
# Set of accepted states
accepting_states = ['State 1']
# The initial state
initial_state = 'State 1'
fsm = FSM(states, alphabet, accepting_states, initial_state)
# Create the set of transitions
transition1 = Transition('State 1', 1, 'State 2')
transition2 = Transition('State 2', 0, 'State 1')
transition3 = Transition('State 1', 0, 'Error')
transition4 = Transition('State 2', 1, 'Error')
transition5 = Transition('Error', 1, 'Error')
transition6 = Transition('Error', 0, 'Error')
transitions = [
transition1,
transition2,
transition3,
transition4,
transition5,
transition6]
# Verify and add them to the FSM
fsm.add_transitions(transitions)
# Now that our FSM is correctly set up, we can give it input to process
# Let's transition the FSM to a green light
should_be_accepted = fsm.accepts([1, 0, 1, 0])
print(should_be_accepted)
# Let's transition the FSM to a red light
should_be_rejected_1 = fsm.accepts([1, 1, 1, 0])
print(should_be_rejected_1)
# Let's transition to yellow and give it bad input
should_be_rejected_2 = fsm.accepts([1, 0, 1, 0, 1, 0, 0])
print(should_be_rejected_2)
有限状态机常见应用
- 自动售卖机
- 交通信号灯
- 电梯
- 闹钟
- 微波炉
- 游戏
交通信号灯：
States:Red, Green and Yellow
Initial State: Green
Accepting States: no
Alphabet: 秒数。
Transitions:
当当前为绿灯，等待360秒，转换为黄灯
当当前为黄灯，等待10秒，转换为红灯
当当前为红灯，等待120秒，转换为绿灯
假设我们正在制作一款动作游戏，其中警卫在地图的某个区域巡逻：
States:Patrol, Attack, Reload, Take Cover, and Deceased.
Initial State: Patrol
Accepting States: Deceased
Alphabet: 为了简单起见，我们可以使用字符串常量来表示世界状态:Player approaches, Player runs, Full health, Low health, No health, Full ammo, and Low ammo.
Transitions:
Patrol
If a player approaches, go to the Attack state.
If we run out of health, go to the Deceased state.
Attack
If ammo is low, go to the Reload state.
If health is low, go to the Take Cover state.
If the player escapes, go to the Patrol state.
If we run out of health, go to the Deceased state.
Reload
If ammo is full, go to the Attack state.
If health is low, go to the Take Cover state.
If we run out of health, go to the Deceased state.
Take Cover
If health is full, go to the Attack state.
If ammo is low, go to the Reload state.
If we run out of health, go to the Deceased state.
