有限状态机

有限状态机器( FSM )或有限状态自动机( FSA ,复数:自动机),有限自动机或简单的状态机是一种数学计算模型。这是一台抽像机器,在任何给定时间都可以恰好位于有限数量的状态之一中。 FSM可以响应某些输入而从一个状态变为另一种状态。从一个状态到另一种状态的变化称为过渡。 FSM由其状态列表,其初始状态和触发每个过渡的输入定义。有限状态机器有两种类型:确定性有限状态机和非确定性有限状态机器。对于任何非确定性的有限状态机器,都可以构建同等的确定性。
在现代社会的许多设备中,可以观察到国家机器的行为,这些设备取决于呈现的事件序列。简单的例子是:自动售货机,当硬币的正确组合沉积时,它们会分配产品;电梯的停车顺序取决于骑手要求的地板;交通信号灯,当汽车在等待时会改变序列;组合锁,需要按正确顺序输入一系列数字。
有限状态机的计算能力少于图灵机等其他一些计算模型。计算功率的区别意味着图灵机可以执行的计算任务,但FSM无法做到。这是因为FSM的内存受到其具有的状态数量的限制。有限状态的机器具有与图灵机相同的计算能力,该计算机受到限制,因此其头可能只能执行“读取”操作,并且总是必须从左向右移动。在自动机理论的更一般领域中研究了FSM。
示例:旋转门的旋转门


可以通过状态机建模的简单机制的一个示例是旋转门。一个用于控制进入地铁和游乐园游乐设施的旋转门是一个门,腰高的三个旋转手臂,一个在入口处。最初,手臂被锁定,阻止了入口,阻止顾客通过。将硬币或令牌存放在旋转门上的插槽中,可以解锁手臂,从而使单个客户可以通过。客户通过后,手臂再次锁定,直到插入另一枚硬币为止。
被视为状态机,旋转门具有两个可能的状态:锁定和解锁。有两个可能影响其状态的输入:将硬币放入插槽硬币并推动手臂推动。在锁定状态下,推动手臂没有效果。无论给出输入推动的次数多少次,它都保持在锁定状态。将硬币放入 - 也就是说,给机器输入了硬币- 将状态从锁定转移到解锁。在未锁定的状态下,将额外的硬币放入没有影响。也就是说,提供其他硬币输入不会改变状态。通过手臂推动的客户可以推动输入并将州重置为锁定。
旋转门机器可以用状态转换表表示,每个可能的状态,它们之间的过渡(基于给出的机器给出的输入)以及每个输入产生的输出:
当前状态 输入 下一个状态 输出 锁定 硬币 解锁 解锁旋转门,以便客户可以通过。 推 锁定 没有任何 解锁 硬币 解锁 没有任何 推 锁定 当客户推动时,将旋转门锁定。
旋转门机器也可以通过称为状态图(上图)的有向图表示。每个状态由节点(圆)表示。边缘(箭头)显示从一个状态到另一个状态的过渡。每个箭头都标有触发过渡的输入。不会导致状态更改的输入(例如未锁定状态的硬币输入)由返回原始状态的圆形箭头表示。从黑点进入锁定节点的箭头表明它是初始状态。
概念和术语
状态是对正在等待执行过渡的系统状态的描述。过渡是在满足条件或收到事件时要执行的一组操作。例如,当使用音频系统聆听无线电(系统处于“无线电”状态)时,接收“下一个”刺激会导致移动到下一个站。当系统处于“ CD”状态时,“下一个”刺激会导致转移到下一个轨道。相同的刺激触发不同的动作,具体取决于当前状态。
在某些有限状态的机器表示中,也可以将动作与状态相关联:
- 入门措施:进入州时执行,并执行
- 退出行动:退出国家时执行。
表示



状态/事件表
使用了几种状态转换表类型。最常见的表示如下所示:当前状态(例如B)和输入(例如y)的组合显示了下一个状态(例如C)。表中没有直接描述完整动作的信息,只能使用脚注添加。使用状态表可以使用FSM定义,包括完整动作的信息(另请参见虚拟有限状态机)。
当前状态
输入
|
陈述a | 州b | 州c |
---|---|---|---|
输入x | ... | ... | ... |
输入y | ... | 州c | ... |
输入z | ... | ... | ... |
UML状态机
统一的建模语言具有描述状态机器的符号。 UML州机器克服了传统有限国家机器的局限性,同时保留其主要收益。 UML状态机介绍了层次嵌套状态和正交区域的新概念,同时扩展了动作概念。 UML状态机具有Mealy机器和Moore机器的特性。他们支持依赖于系统状态和触发事件的动作,例如在Mealy机器中,以及与摩尔计算机一样与状态而不是过渡相关的进入和退出操作。
SDL状态机
规范和描述语言是ITU的标准,其中包含图形符号来描述过渡中的动作:
- 发送活动
- 收到活动
- 启动一个计时器
- 取消计时器
- 启动另一台并发状态机器
- 决定
SDL嵌入称为“抽像数据类型”,动作语言和执行语义的基本数据类型,以使有限状态机器可执行。
其他状态图
有大量的变体代表FSM,例如图3中的FSM。
用法
除了在此处介绍的反应性系统中使用它们外,有限状态机在许多不同的领域都很重要,包括电气工程,语言学,计算机科学,哲学,生物学,数学,视频游戏编程和逻辑。有限状态机是在自动机理论和计算理论中研究的一类自动机。在计算机科学中,有限状态机被广泛用于建模应用行为(控制理论),硬件数字系统,软件工程,编译器,网络协议和计算语言学的设计。
分类
有限状态的机器可以细分为受体,分类器,换能器和音序器。
受体


受体(也称为检测器或识别器)产生二进制输出,表明是否接受收到的输入。受体的每个状态都接受或不接受。一旦收到所有输入,如果当前状态是接受状态,则接受输入;否则将被拒绝。通常,输入是一系列符号(字符);不使用动作。开始状态也可以是一种接受状态,在这种情况下,受体接受空字符串。图4中的示例显示了接受字符串“ nice”的受体。在该受体中,唯一的接受状态是状态7。
如果有一些受体完全接受该集合,则(可能是无限的)符号序列(称为形式语言)是常规语言。例如,具有偶数零数的二进制字符串是一种常规语言(参见图5),而所有长度为质量数的字符串的集合不是。
受体也可以描述为定义一种语言,该语言包含受体接受但没有被拒绝的语言。该语言被接受者接受。根据定义,受体接受的语言是普通语言。
确定给定受体接受的语言的问题是代数路径问题的实例 - 本身就是将最短路径问题的概括性概括为图形,边缘由(任意)半度的元素加权。
图5中出现了接受状态的示例:确定性有限自动机(DFA)检测二进制输入字符串是否包含0s的示例。
S 1 (也是开始状态)表示输入偶数0s的状态。因此,第1条是一种接受状态。如果二进制字符串包含偶数为0(包括任何包含0 no 0s的二进制字符串),则该受体将在接受状态下完成。该受体接受的字符串示例是ε (空字符串),1、11、11 ...,00、010、1010、10110,等。
分类器
分类器是对n严格大于两个的受体产生的受体的概括。
感应器


传感器根据给定的输入和/或使用动作的状态产生输出。它们用于控制应用和计算语言学领域。
在控制应用中,有两种类型的区分:
- 摩尔机器
- FSM仅使用输入操作,即输出仅取决于状态。摩尔模型的优点是简化了行为。考虑一个电梯门。状态机识别两个命令:“ command_open”和“ command_close”,触发状态会更改。进入动作(e :)在状态“打开”中开始打开门的电动机,状态“关闭”的入口动作在另一个方向启动了关闭门的电动机。完全打开或关闭时,状态“打开”和“关闭”停止电动机。它们向外界发出信号(例如,到其他州机器):“门是打开的”或“门是关闭”。
- Mealy Machine
- FSM还使用输入操作,即输出取决于输入和状态。使用MEALY FSM的使用通常导致状态数量减少。图7中的示例显示了一个与摩尔示例相同的行为的MEALY FSM(该行为取决于已实现的FSM执行模型,并且对于虚拟FSM ,例如,例如,对于事件驱动的FSM )。有两个输入操作(i :):“如果command_close到达,则启动电动机关闭门”和“如果command_open到达,则朝另一个方向启动电动机打开门”。未显示“开放”和“关闭”中间状态。
音序器
音序器(也称为发电机)是具有单字母输入字母的受体和换能器的子类。它们仅产生一个序列,可以看作是受体或换能器输出的输出序列。
确定性
确定性( DFA )和非确定性( NFA , GNFA )自动机之间进一步区分。在确定性的自动机中,每个状态都对每个可能的输入都有一个过渡。在非确定性的自动机中,输入可以导致一个,一个以上或没有过渡到给定状态。 PowerSet构造算法可以将任何非确定性自动机转换为具有相同功能的(通常更复杂的)确定性自动机。
只有一个状态的有限状态机称为“组合FSM”。它仅允许在过渡到状态时采取行动。在需要许多有限状态的机器一起工作的情况下,并且很方便地将纯粹的组合部分视为适合设计工具的FSM的一种形式时,此概念很有用。
替代语义
还有其他一组语义可以代表州机器。例如,有一些用于建模和设计嵌入式控制器逻辑的工具。他们将分层状态机器(通常具有一个以上的当前状态),流图和真实表组合为一种语言,从而产生了不同的形式主义和一组语义。这些图表,例如Harel的原始状态机,支持层次嵌套的状态,正交区域,州行动和过渡行动。
数学模型
根据一般分类,可以找到以下正式定义。
确定性有限状态机或确定性有限状态受体是五重奏,其中:
- 是输入字母(有限的非空符号);
- 是一套有限的非空国家;
- 是初始状态,一个元素;
- 是国家转变功能:(在不确定的有限自动机中,即返回一组状态);
- 是最终状态集,一个(可能为空的)子集。
对于确定性和非确定性FSM,允许成为部分函数是常规的,即不必为每个组合定义IE。如果FSM处于状态,则下一个符号是并且未定义,则可以宣布错误(即拒绝输入)。这在通用状态机的定义中很有用,但是在转换机器时有用。默认表格中的某些算法可能需要总功能。
有限状态的机器具有与图灵机相同的计算能力,该计算机受到限制,因此其头可能只能执行“读取”操作,并且总是必须从左向右移动。也就是说,有限状态机器接受的每种正式语言都被这种限制的图灵机所接受,反之亦然。
有限态换能器是二次的,其中:
- 是输入字母(有限的非空符号);
- 是输出字母(有限的非空符号集);
- 是一套有限的非空国家;
- 是初始状态,一个元素;
- 是状态转变函数:;
- 是输出功能。
如果输出函数取决于定义对应于Mealy模型的状态和输入符号(),并且可以将其建模为Mealy Machine。如果输出函数仅取决于定义对应于Moore模型的状态(),并且可以建模为Moore机器。完全没有输出功能的有限状态机被称为半毒剂或过渡系统。
如果我们忽略了摩尔机器的第一个输出符号,则可以通过设置每个Mealy过渡的输出功能(即标记每个边缘)的输出函数,可以轻松地将其转换为等效的MeAly Machine状态。相反的转换较不直接,因为Mealy机器状态在其传入过渡(边缘)上可能具有不同的输出标签。每个这样的状态都需要在多个摩尔机器状态下分开,每个事件输出符号都一个。
最佳化
优化FSM意味着找到具有执行相同功能的最小状态数量的机器。这样做的最快已知算法是Hopcroft最小化算法。其他技术包括使用含义表或摩尔还原程序。另外,可以在线性时间最小化无环FSA。
执行
硬件应用程序

在数字电路中,可以使用可编程逻辑设备,可编程逻辑控制器,逻辑门和FLOP FLOPS或继电器构建FSM。更具体地说,硬件实现需要一个寄存器来存储状态变量,该状态变量是确定状态过渡的组合逻辑块,以及确定FSM输出的第二个组合逻辑块。 Richards Controller是经典的硬件实现之一。
在Medvedev机器中,输出直接连接到状态触发器,最小化触发器和输出之间的时间延迟。
通过对低功率状态机器的状态编码可以优化以最大程度地减少功耗。
软件应用程序
以下概念通常用于使用有限状态机器构建软件应用程序:
有限状态机器和编译器
有限自动机通常用于编程语言编译器的前端。这样的前端可能包括几台有限状态的机器,这些机器实现了词汇分析仪和解析器。从一系列字符开始,词汇分析仪构建了一系列语言令牌(例如保留单词,文字和标识符),解析器构建了语法树。词汇分析仪和解析器处理编程语言语法的常规和无上下文部分。