1. 简介
在本教程中，我们将探讨有限状态机（Finite-State Machine）和马尔可夫链（Markov Chain）之间的区别。这两种模型都是描述时间依赖过程的有力工具，因此将它们放在一起学习是有意义的，因为它们之间确实存在一些关联。
我们会先分别介绍有限状态机和马尔可夫链，然后比较它们的异同，帮助你更好地理解两者的区别。
2. 有限状态机
有限状态机是一种用于表示计算过程的自动机，通常用于模拟计算机中的计算流程。因此，它常作为理论计算机科学课程中第一个计算模型被介绍。
2.1. 状态空间
有限状态机使用“状态”这一概念来建模系统在某一时刻所处的状态及其状态之间的变化。状态的定义通常不在自动机的正式定义中明确给出，它是一个基础概念，通常通过类比来理解。
我们可以将状态理解为“会发生变化的东西”。例如，水在不同温度下会处于固态、液态或气态：
这些状态构成了一个状态空间（state space），我们通常用字母 s 和下标数字表示状态，如 s₀, s₁, s₂, ..., sₙ。
2.2. 规则集或状态转移函数
有限状态机的第二个核心组成部分是状态转移规则，这些规则决定了状态之间的转换方式。我们可以将这些规则视为一个状态转移函数 δ，其作用是将当前状态映射到下一个状态：δ: S → S
最简单的状态转移函数是恒等函数：
∀s ∈ S: δ(s) = s
这意味着系统始终处于同一状态，不会发生变化。
更复杂的状态机可以有更复杂的转移规则，比如循环转移：
δ(sₙ) = sₙ₊₁
如果状态空间是有限的，则最后一个状态必须映射到其他状态或自身，否则该函数不成立。
现代计算机架构的设计中也广泛使用有限状态机来模拟和设计复杂的逻辑流程。
3. 马尔可夫链
3.1. 马尔可夫链定义
马尔可夫链是一种用于描述随机时间依赖过程的模型。与确定性系统不同，马尔可夫链允许状态之间的转换具有随机性，即从当前状态转移到下一状态不仅依赖于当前状态，还包含一定的概率因素。
要描述一个马尔可夫链，我们需要在有限状态机的基础上引入一个概率分布矩阵，该矩阵表示从一个状态转移到另一个状态的概率。
例如，一个包含 n 个状态的马尔可夫链，其状态转移概率矩阵为 n × n 的形式：
1 2 ... n-1 n
1 P(1,1) P(1,2) ... P(1,n-1) P(1,n)
2 P(2,1) P(2,2) ... P(2,n-1) P(2,n)
...
n-1 P(n-1,1) P(n-1,2) ... P(n-1,n-1) P(n-1,n)
n P(n,1) P(n,2) ... P(n,n-1) P(n,n)
每一行的概率总和必须为 1，否则可能属于隐马尔可夫模型（Hidden Markov Model），即系统状态不完全可观测。
3.2. 最简单的马尔可夫链
最简单的马尔可夫链是每个状态只转移到一个确定的下一个状态，对应的转移矩阵每一行只有一个元素为 1，其余为 0。
例如，三个状态循环的情况：
| S₁ | S₂ | S₃ | |
|---|---|---|---|
| S₁ | 0 | 1 | 0 |
| S₂ | 0 | 0 | 1 |
| S₃ | 1 | 0 | 0 |
其状态转移图如下：
3.3. 马尔可夫链与连通性
马尔可夫链不一定必须是完全连通的。它可能包含多个相互连通的子图，而整体是不连通的：
3.4. 马尔可夫链示例应用
在计算机科学中，马尔可夫链常用于建模随机过程。例如，在游戏开发中，我们可以用马尔可夫链来建模一个Boss的行为模式：
Boss有三种行为：防御、攻击、召唤小怪。其状态转移矩阵如下：
| Defend | Attack | Summon | |
|---|---|---|---|
| Defend | 0.6 | 0.3 | 0.1 |
| Attack | 0.9 | 0 | 0.1 |
| Summon | 1 | 0 | 0 |
对应的状态转移图如下：
4. 马尔可夫链与有限状态机是否相同？
现在我们来回答标题的问题：马尔可夫链是否等同于有限状态机？
它们之间有以下相似之处：
✅ 都用于描述时间依赖的过程
✅ 都需要一组状态和状态转移规则
✅ 都只依赖于当前状态，不记录历史
但它们之间有一个关键区别：
❌ 有限状态机是确定性的，而马尔可夫链是概率性的
✅ 当每个状态转移的概率都为 1 时，马尔可夫链退化为有限状态机
✅ 实际应用中，我们通常用马尔可夫链建模非确定性系统，用有限状态机建模确定性系统
5. 总结
在本文中，我们比较了有限状态机和马尔可夫链的异同：
- 两者都用于建模状态随时间变化的系统
- 有限状态机是确定性的，马尔可夫链是概率性的
- 马尔可夫链可以看作是有限状态机在引入概率后的扩展
- 在实际应用中，选择哪种模型取决于系统是否具有随机性
理解这些区别有助于我们在设计系统时选择合适的建模工具。