有限状态机

通过简单的示例快速了解什么是状态机

有很多谈论有限状态机这些天在JavaScript领域。

有个受欢迎的图书馆叫做X状态,最近在GitHub上有超过11000个星星,我最近遇到了这个话题,而且我还在Twitter和其他地方继续阅读有关它的信息。这是一个非常酷的项目。

20年前,我在高中时第一次遇到了有限状态机和自动机,然后在大学的数字设计课程中又遇到了它们。

该数字设计课程涉及编码信息,布尔代数,组合网络,顺序电路,顺序状态机,算术电路,VHDL等内容。

我发现应用于前端工程的有限状态机这一主题非常令人惊奇,然后我回到旧书中,看看是否能找到对它们的很好的解释。

我确实找到了很多信息,当然,作为教科书,事情变得比需要的更为复杂(恕我直言)。我想简化事情,所以我决定为普通人写一些解释,而不是理论上的解释或通过考试的任何解释。您可以应用于现实世界的事物。

状态机

在研究什么是有限状态机之前,我想先介绍一下状态机。

世界充满了状态机。您到处都可以看到它们,但也许您没有想到它们。阅读完本教程后,我确定您会指出现实世界中的对象对您的朋友说:“状态机”(取决于您朋友的书呆子水平)。

最受欢迎和最常见的示例是红绿灯

在任何时间点,流量信号灯都具有定义的状态。通常,它要么:

  • 绿灯亮,其他2灯灭
  • 呈红色亮起,另两个熄灭
  • 当黄灯点亮时,其他2灯熄灭

Traffic lights

(某些信号量略有不同,但出于本示例的考虑,我们不在乎)

在State Machines术语中,称为开灯或关灯输出

这三种情况中的每一种都被称为状态。交通信号灯在接收到输入时将改变状态,通常只是一个固定的计时器,该计时器决定交通信号灯应保持绿色,黄色和红色的时间。

在这种情况下,计时器是输入系统的。一些信号灯具有一个按钮,行人可以按下该按钮以使红色显示在汽车上,这将是另一个输入。

在状态机中,状态只能改变(而我们有一个过渡)以响应输入。

有限状态机

据说我们的交通灯状态机是有限因为我们有有限数量的州。

某些系统可能具有无限数量的状态。

就像世界生态系统模型或昆虫的生命一样。我们不能在有限数量的状态下定义它。

但是交通灯?这很简单,它具有3个状态,就像我们上面说的那样。

我们可以使用更多的有限状态机示例:

  • 自动贩卖机
  • 地铁入口旋转门
  • 加热系统
  • 自动化地铁系统
  • 自动驾驶汽车系统
  • 一部电梯

但是,让我们继续使用我们的交通信号灯示例,它非常简单,我们可以轻松地对此进行推理。

对状态机建模

当然,交通信号灯并不是孤立存在的。那是另一种有限状态机,对于交叉路口每条道路的每一侧所安装的每个交通信号灯设备,它都包含多个不同的有限状态机,这些设备可以同步工作。

Crossroads

现在不要考虑。让我们专注于1个单一的交通信号灯。

如上所述,我们有3个状态,分别可以称为绿色,红色,黄色。

The 3 states

我们有一个初始状态。假设当我们重置它们时,我们的交通灯会在green状态。

Initial state

我们有一个计时器,在绿色状态50秒后,将信号量移到yellow状态。我们有8秒的时间yellow状态,然后我们转到red状态,我们在那儿坐了32秒钟,因为那条路是次要的,应该花更少的时间进行绿化。此后,信号量将恢复为绿色状态,并且循环将无限期继续,直到断电并且信号量在再次获得电源时重置为止。

总共,我们有一个90秒的周期。

这是我们可以建模的方式:

The model

我们也可以使用状态转换表,其中显示了状态机器当前在哪里,什么是输入它收到的是什么下一个状态输出

状态 输入 下一个状态 输出
绿色的 计时器50秒 黄色的 绿灯亮,其他灯灭
黄色的 定时器8秒 红色的 黄灯亮,其他灯灭
红色的 计时器32秒 绿色的 红灯亮,其他灯灭

在我们的简单情况下,给定机器的任何状态,我们只有一个逻辑状态要去,所以我制作的表和图表非常非常简单。

但是,当您的系统开始变得更加复杂时,适当地放置此类图表和分析将非常有帮助,因为与简单地掌握所有内容相比,您可以更轻松地推断出您的应用程序。

具有更复杂状态转换的有限状态机

上面的例子很简单。现在让我们为另一个有限状态机建模。

我们现实世界的情况是这样的:我们有一所房子,有一个门,2个按钮和3个灯。

在默认状态下,所有指示灯均熄灭。

lights

进入房屋后,您可以按一下拥有的2个按钮之一,p1或者p2。当您按下其中任何一个按钮时,l1灯亮。

想象这是入口灯,您可以脱下外套。完成后,您可以决定要进入哪个房间(例如厨房或卧室)。

如果按下按钮p1l1关闭并l2打开。相反,如果您按下按钮p2l1关闭并l3打开。

再次按下2个按钮中的任何一个,p1或者p2,当前亮起的灯将熄灭,我们将回到系统的初始状态。

这个有限状态机比第一个有限状态机要复杂一些,因为这次我们可以根据输入有多个路由。

让我们对此建模。

我们基本上有4种状态:

  • 没有灯亮
  • l1打开
  • l2打开
  • l3打开

model lights

我们有2个输入:

  • p1
  • p2

如果我们从初始状态开始,并且尝试根据随时间推移触发输入的方式来建模可能发生的所有事情,那么最终结果是:

State transitions

可以使用此表对其进行汇总:

状态 输入 下一个状态
没有灯亮 p1 l1打开
没有灯亮 p2 l1打开
l1打开 p1 l2打开
l1打开 p2 l3打开
l2打开 p1 没有灯亮
l2打开 p2 没有灯亮
l3打开 p1 没有灯亮
l3打开 p2 没有灯亮

这是一个简短的解释,但也许会使事情“点击”。


更多计算机教程: