有限状态机原理_无限状态机「建议收藏」

大家好，欢迎来到IT知识分享网。

有限状态机概述

有限状态机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.

转载请注明出处，以上只代表个人观点，引用不当或侵权请联系删除。