2.1.1 有限状态机的基本概念

有限状态机（Finite State Machine，FSM）也称有限状态自动机或有限自动机，是表示有限个状态以及在这些状态之间的转移等行为的形式化模型。有限状态机用于描写一个状态在何种条件下转移到另一个状态，描述状态控制流和转移流。

定义2.1（有限状态机） 有限状态机形式化地定义为4元组(S,I,f,s₁)，其中S是有限状态集{s₁,s₂,…,s_n}，其元素称为状态；I是输入集{i₁,i₂,…,i_m}，其元素称为输入；f是状态转移函数(f:S×I→S)，一般是偏函数，即在一部分元素上有定义；s₁是初始状态。

一个有限状态机可用带权值的有向图表示，如图2-1所示。

图2-1中的有限状态机含有4个状态s₁、s₂、s₃和s₄，2个输入0和1，以及4个状态转移：s₁→s₂、s₁→s₃、s₂→s₄和s₃→s₄。这些状态转移与输入有关系，系统的输入触发了系统状态的转移，因此系统输入成了系统状态转移的触发因素。比如，s₁是初始状态，在s₁状态下，当输入元素为0时，自动机从状态s₁转移到状态s₂；而当输入元素为1时，自动机从状态s₁转移到状态s₃。

有限状态机的状态一般表示系统的功能，或者工作状态。如自动门的开状态和关状态，交通灯的红灯状态、绿灯状态和黄灯状态。输入是指有限状态机可以输入的元素，使系统与外界实现了交互，在不同的实际系统中表现形式是不一样的。如自动门的输入是控制信号，表示开信号或关信号；交通灯的输入也是控制信号，表示红灯亮、黄灯亮或绿灯亮。状态转移函数规定了在输入某元素情况后状态的转移情况。如自动门当前状态是关，当输入是开门信号时，状态转移到开。交通灯当前状态是红灯亮，当输入是绿灯信号时，状态转移到绿灯亮。