数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究解释构造最小有限状态自动机的 方法。
有限状态机 (FSM) 有一组状态和两个称为下一状态和输出函数的函数。
状态集对应于内部存储的所有可能组合。
如果有 n 位存储，则有 2n 个可能的状态。
下一状态函数是一个组合逻辑函数，它根据输入和当前状态确定系统的下一状态。
有限状态机由以下部分组成：
- K 个状态：S = {s1, s2, ... ,sk}，s1 是初始状态
- N 个输入：I = {h, i2, ... ,in}
- M 个输出：O = {o1, o2, . ,om}
下一状态函数 T(S, I) 用于映射每个当前状态并给出输入到下一状态。输出函数 P(S) 指定输出。
FSM 的最小化意味着减少给定 FA 的状态数。因此，在最小化 FSM 后，我们得到了具有冗余状态的 FSM。
在最小化 FSM 时，我们首先找出哪些两个状态是等价的。如果两个状态是等价的，那么我们可以用一个代表状态来表示这两个状态。
如果对于所有 x ∈ Σ*（Σ* 表示任意长度的任意字符串），δ(q1,x) 和 δ(q2,x) 都是最终状态或它们都是非最终状态，则两个状态 q1 和 q2 是等价的。
我们可以通过查找等价状态来最小化给定的 FSM。
方法
构造最小有限状态自动机的方法如下所述：
**步骤 1** - 创建一个集合 S0 作为 S0={Q01, Q02}，其中 Q01 是所有最终状态的集合，而 Q02 = Q-Q01，其中 Q 是 DFA 中所有状态的集合。
**步骤 2** - 从 Sk 构造 Sk+1。
令 Qik 为 S0 中的任何子集。如果 q1 和 q2 在 Qik 中，则如果 δ(q1,a) 和 δ(q2,a) 是 K 等价的，则它们是 (k+1) 等价的。找出 δ(q1,a) 和 δ(q2,a) 是否驻留在同一个等价类 δ0 中。
然后，据说 q1 和 q2 是 (k+1) 等价的。因此，Qik 进一步划分为 (k+1) 个等价类。
**步骤 3** - 对 Sk 中的每个 Qik 重复步骤 2，并获得 Sk+1 的所有元素。
**步骤 4** - 为 n=1,2,3,…..构造 Sn，直到 Sn=Sn+1。
**步骤 5** - 然后，用代表状态替换一个等价类中的所有等价状态。
2K+ 次查看
