有限状态机(FSM)初探

类别:软件工程 点击:0 评论:0 推荐:

NIST 对有限状态机(Finite State Machine, FSM)的定义如下。
 
    包含一组状态集(states)、一个起始状态(start state)、一组输入符号集(alphabet)、一个映射输入符号和当前状态到下一状态的转换函数(transition function)的计算模型。当输入符号串,模型随即进入起始状态。它要改变到新的状态,依赖于转换函数。在有限状态机中,会有有许多变量,例如,状态机有很多与动作(actions)转换(Mealy机)或状态(摩尔机)关联的动作,多重起始状态,基于没有输入符号的转换,或者指定符号和状态(非定有限状态机)的多个转换,指派给接收状态(识别者)的一个或多个状态,等等。

    一个例子

                    

    上图是一个接受者 FSM 模型,用来分析单词“nice”。该分析器只接受字符输入,包含6种状态,状态切换由输入的字符驱动。理解起来非常简单,在此不作解释了。

    感谢宏云前辈对本文翻译提供的指导。

              

(请注意!引用、转贴本文应注明原作者:Rosen Jiang 以及出处:http://blog.csdn.net/rosen

本文地址:http://com.8s8s.com/it/it32119.htm