什么是理论计算机科学中的有限状态机？

有限状态机具有一组状态和两个称为下一状态和输出函数的函数。

  • 状态集对应于内部存储的所有可能组合。如果存在 n 位存储，则存在 2n 种可能的状态。
  • 下一状态函数是一个组合逻辑函数，它根据输入和当前状态确定系统的下一状态。

下图解释了理论计算机科学中有限状态机的功能。

输出函数根据当前状态和输入生成一组输出。

类型

有限状态机的两种类型为：

  • Moore 机 - 在 Moore 机中，输出仅取决于当前状态。
  • Mealy 机 - 在 Mealy 机中，输出取决于当前状态和当前输入。

我们主要处理 Moore 机。这两种类型在功能上是等价的。

有限状态机包含以下内容：

  • K 个状态：S = {s1, s2, ... ,sk}，s1 是初始状态
  • N 个输入：I = {h, i2, ... ,in}
  • M 个输出：O = {o1, o2, . ,om}
  • 下一状态函数 T(S, I)：用于将每个当前状态和输入映射到下一个状态。
  • 输出函数 P(S)：此函数指定输出。

组件

有限状态机中存在的组件解释如下：

状态 - 状态通常用圆圈绘制，并且一次只能激活一个状态。

表示如下：

初始状态 - 它是我们系统的起点。初始状态通常用指向状态的箭头绘制，如下所示：

最终状态 - 它是我们已知状态的子集，指示我们处理的输入是否有效。接受状态通常绘制为双圆圈，如下所示：

转换 - 机器从一个状态转换到另一个状态，并表示为转换。这些以两条状态用线连接的方式绘制，如下所示：

更新于： 2021年6月11日

8K+ 次浏览

启动你的 职业生涯

通过完成课程获得认证

开始学习
广告