有限状态自动机(finite state automata)或有限状态机(finite state machine)，是一个简单的数学模式，具有离散式输入的有限集合，与通过一个根据被接受到输入的次序所决定的有限状态集合。自动机可能具有一个有限集合的输出。如果是这样，则自动机将会产生一连串的输出以反映出一连串的输入。换币机、升降机、自动贩卖机，与车库开门器是根据模型的机器的例子。在计算器科学的许多领域中，有限状态是非常有用的设计模型，包括编译器中的语汇扫瞄，以计算协议之定义，与交换电路。
下面说明了如何用自动机来塑造一个简单的装置。下图说明对于车库开门器操作情形的一个状态模型，以标记图或状态图表示出。假设由两个按钮来控制门：一个称为开扭而另一个称为关扭。门的四个状态以圆圈表示记为关闭、上升、下降及打开。此描述了车库之门操作的情形。
车库开门器的状态模型
当门是在关闭状态，按开钮会使得门进入上升状态，于此期间在马达控制之下，门将逐渐的开启。在门完全打开之后，即进入关闭状态。再按关钮会使门进入下降状态，于此期间门将逐渐的关闭。从状态途中可以清楚的看出门不能立即地从打开状态至关闭状态，反过来亦如此。而且，也可能轮流的按开钮与关扭，使门在上升与下降状态之间转变，使得门的动作像玩偶一样。最后，此模型说明当门是在关闭状态时按关钮或者门是在打开状态时按开钮，将不会引起任何状态的改变，所以什么事情都不会发生。在马达控制门时会侦测『完全关闭』以及『完全打开』之事件，以分离按钮的机械装置。
当门是在某一特殊状态时，我们可将有限状态自动机的输出想成送给马达控制用的控制信号。在其它的情况下，则没有可确认的输出。我们只感兴趣于机器对一连串输入的反应所产生的状态。对于自动机的研究我们将分为具有输出的自动机与不具输出的自动机。
现在我们正式地介绍有限状态机的抽象模式。有限状态是由下列各项规则所决定的：
- 状态有限集S={S0,S1,S2, ...... }。
- 集合S的特殊元素S0，即为起始状态(initail state)。
- 输入字母有限集I={i1,i2, ...... }。
- 输出字母有限集O={o1,o2, ...... }。
- S×I映至S的函数f，即转换函数(transition function)。
- S映至O的函数g，即为输出函数(output function)。
在任何时刻中，有限状态机皆处于某一状态中。当输入字母进入时，此机器则经由转换函数转换到另一状态中。而且，此机器依据输出函数而造出一个输出字母。如表二所示的列表方式能够很方便地描述有限状态机。对于表二所示的有限状态机而言，其集合为{S0,S1,S2,S3,S4,S5,S6}，其输入字母集为{a,b,c}，而输出字母集为{0,1}。在S0上的双线箭头表示S0为起始状态。在表二(a)中，列有转换函数f，其中在一列（对应于状态Sp）与一行（对应于输入字母之q）交点上的状态即为f(Sp,ip)的值。表二(b)中列有输出函数。
范型实现
/*
* 抽象有限状态机模板
* 四个规则：
* 1.状态有限集合S={S0,S1,S2, ...... }。
* 2.集合S的特殊元素S0，即为初始状态(initail state)。
* 3.输入有限集I={i1,i2, ...... }。
* 4.输出有限集O={o1,o2, ...... }。
*/
template <class StateType,class InputType,class OutputType>
class FSM
{
public:
//构造函数
FSM(const set<StateType>& States,//状态有限集合S={S0,S1,S2, ...... }。
const set<InputType>& Inputs,//输入有限集I={i1,i2, ...... }。
const set<OutputType>& Outputs,//输出有限集O={o1,o2, ...... }。
const StateType& InitState)://集合S的特殊元素S0，即为初始状态(initail state)
m_States(States),m_Inputs(Inputs),
m_Outputs(Outputs),m_CurrentState(InitState)
{
assert(States.size()>0);
assert(States.find(InitState)!=States.end());
}
//获取当前状态
StateType CurrentState() const
{
return m_CurrentState;
}
//根据输入值改变状态，返回改变以后状态机的当前状态
StateType ChangeState(const InputType& Input)
{
m_CurrentState=Transition(Input);
return Output(m_CurrentState);
}
//状态有限集合S={S0,S1,S2, ...... }。
const set<StateType> m_States;
//输入有限集I={i1,i2, ...... }。
const set<InputType> m_Inputs;
//输出有限集O={o1,o2, ...... }。
const set<OutputType> m_Outputs;
protected:
//5.I映至S的函数f，即转换函数(transition function)。
virtual StateType Transition(const InputType& Input) const=0;
//6.S映至O的函数g，即为输出函数(output function)。
virtual OutputType Output(const StateType& State) const=0;
//析构函数
virtual ~FSM(void)=0{}
private:
//当前状态
StateType m_CurrentState;
};
|
|
