自动机是计算机的简单理论模型通常将自动机分为有限自动机和图灵机。尽管有限自动机更简单但在定义图灵机之后数年,这个概念才被提出来
沃伦·麦卡洛克当时正在研究脑部创伤治疗精神病人,他想研究出一种解释大脑如何工作的理论。沃尔特·皮茨最初被培养成为一位逻辑学学者,但是却在全噺的数学生物物理学领域发表论文两人于1942年相识,认识到他们对相同类型的问题感兴趣于是开始联手研究彼此取长补短。他们发表了苐一篇论文“神经活动中内在的思想逻辑演算”(A Logical Calculus of Ideas
Activity)在这篇论文中,他们借助细胞对神经元进行了建模虽然每个细胞都有多个输入,泹只有一个输出一个细胞的输出必须成为另一个细胞的输入,输入的类型有两种——抑制的和兴奋的如果兴奋的输入超过了一定阈值,且没有抑制输入细胞将会被激活。虽然细胞的集合和它们之间的连接被两人称为神经网络但他们没有意识到,这是大脑实际运作的簡化模型通过研究神经网络可以得知神经网络如何处理逻辑活动。他们的网络模型与神经元和人类的大脑具备相同的特征因此他们希朢自己的研究能够揭示人类逻辑推理的奥秘。
他们的论文引起了计算机专家约翰·冯·诺依曼和著名的数学家、哲学家诺伯特·维纳的注意两位学者对这篇论文印象深刻。维纳看到了其中蕴含的力量他意识到,这一观点具有广泛的适应性可以发展出控制论。控制论将催苼可以学习的机器的理念反过来也会孕育人工智能。冯·诺依曼认识到,麦卡洛克和皮茨对细胞和细胞间连接的描述,同样可以应用到电子组件和计算中。他在《关于EDVAC的报告》(First
draft of a report on the EDVAC)一文中对此进行了详细的描述正是这篇论文奠定了现代计算机构建的基石。
另一个受到麦鉲洛克和皮茨影响的人是马文·明斯基,1954年明斯基在他的博士论文中对神经网络进行了研究展示了如何使用这些网络对自动机进行全面嘚描述。明斯基的著作《计算:有限和无限机器》是这一领域的经典之作高屋建瓴地描述了自动机和计算理论。通过对比物理学明斯基在这本书的前言中解释了这种使用理论机器研究的理论为什么是状态机能够发挥作用。
与物理学使用统计定义事件的方法不同我们是鼡逻辑定义的计算或表达式。它们被联系在一起不是通过几何或能量性质,而是通过它们与类似机器或类似定义之间的关系我们能够使用机器组件进行简单的交互,应用最显而易见的逻辑命题面对等价的现实物理机器时,我们必须解决极端复杂的分析等式
自动机被劃分为两类:一类具有有限内存,另一类具有无限内存下面只研究有限的一类
有限状态机(Finite State Machine,FSM)是一种抽象的机制 它包括有限数量的狀态。因此FSM是一个状态集值的一个有限集合。
闸机是一个常见的状态机这是《敏捷软件开发——原则、模式与实战》一书中展示的一個经典示例。在这里将以香港地铁站的闸机为例介绍有限状态机,其用例文本摘要如下:
通常闸机默认是关闭的当闸机收到有效卡信息时,则打开闸机;当乘客通过后则关闭闸机。如果有人非法通过则闸机会发出连续的“滴、滴、滴……”报警声;如果闸机已经打開,而乘客还在刷卡则闸机会发出“滴”的声音提示乘客,并显示“票价和余额闸机已经打开,请通过谢谢!”
FSM会响应“事件”而妀变状态,即将每个“事件”实现为一个函数当“事件”发生时,就意味着调用了一个函数FSM也执行动作产生输出,所执行的动作是当湔状态和输入事件的一个函数其目的是执行系统的任务。
事件是指在某个时刻发生的事情比如,闸机的“刷卡(card)”事件和“通过(pass)”事件状态是系统的状态。事件表示时间点状态表示时间段,状态对应对象接收的两次事件之间的时间间隔比如,闸机可能处于嘚状态:Locked状态和Unlocked状态
转换是从一个状态转移为另一个状态的路径,引发它的事件被称为事件触发器简称触发。而转换可以触发动作——表示对象的某个方法的调用比如,当事件card发生时闸机从Locked状态转换为Unlocked状态并执行打开闸机动作。转换还有一个监护条件逻辑测试——戓布尔测试只有测试通过时转换才发生。
而事件可以是外部事件和内部事件外部事件是在系统和它的执行者之间传递的事件,比如按下一个键和一个来自传感器的中断都是外部事件。内部事件是在系统内部的对象之间传送的事件比如,溢出异常是一个内部事件可鉯用UML对4种事件建模:信号、调用、时间推移或状态的一次改变。信号或调用可以带有参数参数值对转移(包括监护条件和动作的表达式)是可见的。
信号是一个异步事件在实例间异步传递消息的通信规约。消息是一个具名对象信号是消息的类型,象类一样信号也有屬性和操作。而信号事件是指发送或接收信号的事件其差别在于信号是对象之间的消息,而信号事件是指在某时某刻发生的事情
如果倳件没有产生任何效果,则FSM保持状态不变通常下一个状态依赖于当前状态和输入事件,有时状态转移会导致输出动作在某些情况下,雖然一个事件不会立即导致状态转换但它会影响随后的状态转换。如果事件已经产生则可以将该情况保存为一个条件,在之后进行检驗
监护条件是由一个方括号括起来的布尔表达式,放在触发器事件的后面其表示法为“事件[条件]”(Event[Condition]),条件是某一段时间内值为True或False通常“事件”引起了“状态转换”,当事件发生时为了发生转换,可选的“条件”的值必须为True可选的“动作”作为结果被执行。
动莋是与状态转换相关的可选的输出动作执行了计算(调用相应的函数),作为状态转换的结果事件导致状态转移,而动作是状态转移所产生的效果动作在状态转移时被触发,执行后自行终止
转换动作是指从某一状态转换为另一状态时产生的动作,该动作也可能发生茬状态转换至自身状态时为了描述状态图中的动作,将状态转换表示为:事件/动作(Event/Action)或事件[条件]/动作(Event[Condition]/Action)比如,card/unlock
考虑闸机状态图Φ的动作:当事件card发生时,闸机从Locked状态转换为Unlocked状态发生在该状态转移中的动作是获取card信息。作为状态机的输出该动作显示票价和余额並开锁。
通常多个动作可以和同一个状态转换关联因为动作都是并发执行的,所以这些动作之间不能有任何的相互依赖关系比如,不能同时发生两个并发的事件——计算余额和显示余额因为这两个动作有先后顺序的依赖关系,在余额计算之前不无法显示出来为了避開这个问题,可以引入“计算余额”的中间状态动作“计算余额”在进入该状态时执行,动作“显示余额”在退出该状态时执行
进入動作是指在开始进入该状态时触发的即时动作,使用保留字“进入(entry)”表示在状态框里表示为“进入/动作(entry/Action),即entry/[action-list]”
退出动作是指茬离开该状态时触发的即时动作,使用保留字“退出(exit)”表示在状态框里表示为“退出/动作(exit/Action),即exit/[action-list]”
由于状态图源自于用例,因此要从用例开发状态图首先需要用例中的一个特定的场景,即从用例中的一条特定路径描述对象之间的交互正常的业务序列详见图 4.8(a)。
如果闸机在Locked状态收到card事件则转移到Unlocked状态并执行unlock动作,此时闸机将它的状态改为Unlocked并调用unlock函数;如果闸机在Unlocked状态收到一个pass事件则转移箌Locked状态并执行lock动作,此时闸机将它的状态改为Locked并调用lock函数
如图 4.9 (a)所示为正常的业务序列图对应状态图,由于闸机处于打开状态或关闭状态時“card()”或“pass()”操作对应的处理是不同的,因此难以用一个序列图清晰地描绘对象交互与状态的关系如果以业务实体(闸机)的状态(咑开状态或关闭状态)为核心,将执行者与系统交互的具体操作称之为“事件”比如,card()、pass()等
图 4.9 闸机状态图
表4.1 闸机状态转移表
这些图是甴状态、事件、转换和动作组成的有向图,圆角矩形表示闸机的状态闸机始终保持状态直到转换促使它改变状态。转换用导向箭头表示通常由收到触发事件的元素发起。当输入的事件与有向边上的事件匹配时闸机将会从一个状态转换到另一个状态。
其中包含了起始状態、触发转移事件、终止状态和要执行的动作将其转换为状态转移表的表格,详见表 4.1由于状态转移表列出了所有状态下,接收所有事件后的状态是如何变化的因此很容易帮助发现遗漏了哪些状态转移。虽然状态转移表的优点是直观但其缺点也是非常明显的,那就是難以确认状态转移的完整性
显然,通用状态图与状态表描述状态机的行为开发者可以很容易检查那些未知的,甚至没有处理的情况仳如,闸机在Unlocked状态下没有处理card事件的转移且在Locked状态下也没有处理pass事件的转移。假设如果闸机在Locked状态收到一个非法pass事件则状态不变并执荇alarm动作,其业务序列图详见图
4.8(b)如果乘客不熟悉流程,当闸机已经转移到Unlocked状态时而乘客还在刷卡(card),则闸机会发出“滴”的声音提示乘客并显示“票价和余额,闸机已经打开请通过,谢谢!” 其业务序列图详见图 4.8(c)完整的闸机状态转移表详见表
表 4.2 完整的闸機状态转移表
在关闭状态下,当需要增加报警功能时只需要新增一条事件/动作线,详见图 4.9 (b)同理,增加一条事件/动作线表示闸门在已经咑开时继续刷卡的情况详见图
4.9 (c)。由于这两种情况不会改变闸机的状态因此导向箭头起始和结束均为同一状态。
在公众号后台回复关键芓“程序设计”即可在线阅读《程序设计与数据结构》;回复关键字“编程”,即可在线阅读《面向AMetal框架与接口的编程(上)》