有限状态机

Combinational logic Finite-state machine Pushdown automaton Turing machine Automata theory
自动机的类

有限状态机器FSM )或有限状态自动机FSA ,复数:自动机),有限自动机或简单的状态机是一种数学计算模型。这是一台抽像机器,在任何给定时间都可以恰好位于有限数量的状态之一中。 FSM可以响应某些输入而从一个状态变为另一种状态。从一个状态到另一种状态的变化称为过渡。 FSM由其状态列表,其初始状态和触发每个过渡的输入定义。有限状态机器有两种类型:确定性有限状态机非确定性有限状态机器。对于任何非确定性的有限状态机器,都可以构建同等的确定性。

在现代社会的许多设备中,可以观察到国家机器的行为,这些设备取决于呈现的事件序列。简单的例子是:自动售货机,当硬币的正确组合沉积时,它们会分配产品;电梯的停车顺序取决于骑手要求的地板;交通信号灯,当汽车在等待时会改变序列;组合锁,需要按正确顺序输入一系列数字。

有限状态机的计算能力少于图灵机等其他一些计算模型。计算功率的区别意味着图灵机可以执行的计算任务,但FSM无法做到。这是因为FSM的内存受到其具有的状态数量的限制。有限状态的机器具有与图灵机相同的计算能力,该计算机受到限制,因此其头可能只能执行“读取”操作,并且总是必须从左向右移动。在自动机理论的更一般领域中研究了FSM。

示例:旋转门的旋转门

旋转门的状态图
一个旋转门

可以通过状态机建模的简单机制的一个示例是旋转门。一个用于控制进入地铁和游乐园游乐设施的旋转门是一个门,腰高的三个旋转手臂,一个在入口处。最初,手臂被锁定,阻止了入口,阻止顾客通过。将硬币或令牌存放在旋转门上的插槽中,可以解锁手臂,从而使单个客户可以通过。客户通过后,手臂再次锁定,直到插入另一枚硬币为止。

被视为状态机,旋转门具有两个可能的状态:锁定解锁。有两个可能影响其状态的输入:将硬币放入插槽硬币并推动手臂推动。在锁定状态下,推动手臂没有效果。无论给出输入推动的次数多少次,它都保持在锁定状态。将硬币放入 - 也就是说,给机器输入了硬币- 将状态从锁定转移到解锁。在未锁定的状态下,将额外的硬币放入没有影响。也就是说,提供其他硬币输入不会改变状态。通过手臂推动的客户可以推动输入并将州重置为锁定

旋转门机器可以用状态转换表表示,每个可能的状态,它们之间的过渡(基于给出的机器给出的输入)以及每个输入产生的输出:

当前状态 输入 下一个状态 输出
锁定 硬币 解锁 解锁旋转门,以便客户可以通过。
锁定 没有任何
解锁 硬币 解锁 没有任何
锁定 当客户推动时,将旋转门锁定。

旋转门机器也可以通过称为状态图(上图)有向图表示。每个状态由节点)表示。边缘(箭头)显示从一个状态到另一个状态的过渡。每个箭头都标有触发过渡的输入。不会导致状态更改的输入(例如未锁定状态的硬币输入)由返回原始状态的圆形箭头表示。从黑点进入锁定节点的箭头表明它是初始状态。

概念和术语

状态是对正在等待执行过渡的系统状态的描述。过渡是在满足条件或收到事件时要执行的一组操作。例如,当使用音频系统聆听无线电(系统处于“无线电”状态)时,接收“下一个”刺激会导致移动到下一个站。当系统处于“ CD”状态时,“下一个”刺激会导致转移到下一个轨道。相同的刺激触发不同的动作,具体取决于当前状态。

在某些有限状态的机器表示中,也可以将动作与状态相关联:

  • 入门措施:进入州时执行,并执行
  • 退出行动:退出国家时执行。

表示

图1 UML状态图示例(烤面包机)
图2 SDL状态机示例
图3简单的有限状态机的示例

状态/事件表

使用了几种状态转换表类型。最常见的表示如下所示:当前状态(例如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:受体FSM:解析字符串“ nice”。
图5:受体的表示;此示例显示了一个确定二进制号是否具有偶数为0的示例,其中s 1是一种接受状态,而s 2是非接受状态

受体(也称为检测器识别器)产生二进制输出,表明是否接受收到的输入。受体的每个状态都接受不接受。一旦收到所有输入,如果当前状态是接受状态,则接受输入;否则将被拒绝。通常,输入是一系列符号(字符);不使用动作。开始状态也可以是一种接受状态,在这种情况下,受体接受空字符串。图4中的示例显示了接受字符串“ nice”的受体。在该受体中,唯一的接受状态是状态7。

如果有一些受体完全接受该集合,则(可能是无限的)符号序列(称为形式语言)是常规语言。例如,具有偶数零数的二进制字符串是一种常规语言(参见图5),而所有长度为质量数的字符串的集合不是。

受体也可以描述为定义一种语言,该语言包含受体接受但没有被拒绝的语言。该语言被接受者接受。根据定义,受体接受的语言是普通语言

确定给定受体接受的语言的问题是代数路径问题的实例 - 本身就是将最短路径问题的概括性概括为图形,边缘由(任意)半度的元素加权

图5中出现了接受状态的示例:确定性有限自动机(DFA)检测二进制输入字符串是否包含0s的示例。

S 1 (也是开始状态)表示输入偶数0s的状态。因此,第1条是一种接受状态。如果二进制字符串包含偶数为0(包括任何包含0 no 0s的二进制字符串),则该受体将在接受状态下完成。该受体接受的字符串示例是ε空字符串),1、11、11 ...,00、010、1010、10110,等。

分类器

分类器是对n严格大于两个受体产生的受体的概括。

感应器

图6传感器FSM:摩尔模型示例
图7传感器FSM:MEALY模型示例

传感器根据给定的输入和/或使用动作的状态产生输出。它们用于控制应用和计算语言学领域。

在控制应用中,有两种类型的区分:

摩尔机器
FSM仅使用输入操作,即输出仅取决于状态。摩尔模型的优点是简化了行为。考虑一个电梯门。状态机识别两个命令:“ command_open”和“ command_close”,触发状态会更改。进入动作(e :)在状态“打开”中开始打开门的电动机,状态“关闭”的入口动作在另一个方向启动了关闭门的电动机。完全打开或关闭时,状态“打开”和“关闭”停止电动机。它们向外界发出信号(例如,到其他州机器):“门是打开的”或“门是关闭”。
Mealy Machine
FSM还使用输入操作,即输出取决于输入和状态。使用MEALY FSM的使用通常导致状态数量减少。图7中的示例显示了一个与摩尔示例相同的行为的MEALY FSM(该行为取决于已实现的FSM执行模型,并且对于虚拟FSM ,例如,例如,对于事件驱动的FSM )。有两个输入操作(i :):“如果command_close到达,则启动电动机关闭门”和“如果command_open到达,则朝另一个方向启动电动机打开门”。未显示“开放”和“关闭”中间状态。

音序器

音序器(也称为发电机)是具有单字母输入字母的受体和换能器的子类。它们仅产生一个序列,可以看作是受体或换能器输出的输出序列。

确定性

确定性DFA )和非确定性NFAGNFA )自动机之间进一步区分。在确定性的自动机中,每个状态都对每个可能的输入都有一个过渡。在非确定性的自动机中,输入可以导致一个,一个以上或没有过渡到给定状态。 PowerSet构造算法可以将任何非确定性自动机转换为具有相同功能的(通常更复杂的)确定性自动机。

只有一个状态的有限状态机称为“组合FSM”。它仅允许在过渡状态时采取行动。在需要许多有限状态的机器一起工作的情况下,并且很方便地将纯粹的组合部分视为适合设计工具的FSM的一种形式时,此概念很有用。

替代语义

还有其他一组语义可以代表州机器。例如,有一些用于建模和设计嵌入式控制器逻辑的工具。他们将分层状态机器(通常具有一个以上的当前状态),流图和真实表组合为一种语言,从而产生了不同的形式主义和一组语义。这些图表,例如Harel的原始状态机,支持层次嵌套的状态,正交区域,州行动和过渡行动。

数学模型

根据一般分类,可以找到以下正式定义。

确定性有限状态机或确定性有限状态受体是五重奏,其中:

  • 是输入字母(有限的非空符号);
  • 是一套有限的非空国家;
  • 是初始状态,一个元素;
  • 是国家转变功能:(在不确定的有限自动机中,即返回一组状态);
  • 是最终状态集,一个(可能为空的)子集。

对于确定性和非确定性FSM,允许成为部分函数是常规的,即不必为每个组合定义IE。如果FSM处于状态,则下一个符号是并且未定义,则可以宣布错误(即拒绝输入)。这在通用状态机的定义中很有用,但是在转换机器时有用。默认表格中的某些算法可能需要总功能。

有限状态的机器具有与图灵机相同的计算能力,该计算机受到限制,因此其头可能只能执行“读取”操作,并且总是必须从左向右移动。也就是说,有限状态机器接受的每种正式语言都被这种限制的图灵机所接受,反之亦然。

有限态换能器是二次的,其中:

  • 是输入字母(有限的非空符号);
  • 是输出字母(有限的非空符号集);
  • 是一套有限的非空国家;
  • 是初始状态,一个元素;
  • 是状态转变函数:;
  • 是输出功能。

如果输出函数取决于定义对应于Mealy模型的状态和输入符号(),并且可以将其建模为Mealy Machine。如果输出函数仅取决于定义对应于Moore模型的状态(),并且可以建模为Moore机器。完全没有输出功能的有限状态机被称为半毒剂或过渡系统。

如果我们忽略了摩尔机器的第一个输出符号,则可以通过设置每个Mealy过渡的输出功能(即标记每个边缘)的输出函数,可以轻松地将其转换为等效的MeAly Machine状态。相反的转换较不直接,因为Mealy机器状态在其传入过渡(边缘)上可能具有不同的输出标签。每个这样的状态都需要在多个摩尔机器状态下分开,每个事件输出符号都一个。

最佳化

优化FSM意味着找到具有执行相同功能的最小状态数量的机器。这样做的最快已知算法是Hopcroft最小化算法。其他技术包括使用含义表或摩尔还原程序。另外,可以在线性时间最小化无环FSA。

执行

硬件应用程序

图9 4位TTL计数器的电路图,一种状态机器

数字电路中,可以使用可编程逻辑设备可编程逻辑控制器逻辑门FLOP FLOPS继电器构建FSM。更具体地说,硬件实现需要一个寄存器来存储状态变量,该状态变量是确定状态过渡的组合逻辑块,以及确定FSM输出的第二个组合逻辑块。 Richards Controller是经典的硬件实现之一。

Medvedev机器中,输出直接连接到状态触发器,最小化触发器和输出之间的时间延迟。

通过对低功率状态机器的状态编码可以优化以最大程度地减少功耗。

软件应用程序

以下概念通常用于使用有限状态机器构建软件应用程序:

有限状态机器和编译器

有限自动机通常用于编程语言编译器的前端。这样的前端可能包括几台有限状态的机器,这些机器实现了词汇分析仪和解析器。从一系列字符开始,词汇分析仪构建了一系列语言令牌(例如保留单词,文字和标识符),解析器构建了语法树。词汇分析仪和解析器处理编程语言语法的常规和无上下文部分。

也可以看看