如何用有限状态机（FSM）正确建模组合逻辑？附与门示例疑问

组合逻辑的核心特点是无记忆性：输出仅由当前输入决定，与历史状态无关。它属于有限状态机的退化特例，可通过Mealy机或Moore机直接建模，关键是要贴合"无记忆"的特性设计状态和转移规则。

1. 用Mealy机建模AND门 #

Mealy机的输出由当前状态与输入共同决定，对于无记忆的组合逻辑，我们只需要一个固定状态（无需存储历史）：

• 唯一状态：s0
• 输入集合：所有(A,B)组合：(0,0)、(0,1)、(1,0)、(1,1)
• 转移规则：所有输入都从s0转移回s0（状态不变化，体现无记忆）
• 输出规则：在转移边上标注对应输出：
  • 输入(0,0)/(0,1)/(1,0) → 输出0
  • 输入(1,1) → 输出1

状态图简化表示：

(0,0)/0, (0,1)/0, (1,0)/0
          ┌──────────────────────────┐
          ▼                          │
┌──────────────────┐                 │
│      s0          │ ◄───────────────┘
└──────────────────┘
          │
          │ (1,1)/1
          ▼
          (回到s0)

2. 用Moore机建模AND门 #

Moore机的输出由当前状态直接决定，因此需要两个状态分别对应AND门的两种输出：

• 状态定义：
  • s0：输出0
  • s1：输出1
• 转移规则（核心：转移仅由输入决定，与当前状态无关）：
  • 无论当前处于s0还是s1，输入为(1,1)时，转移到s1
  • 无论当前处于s0还是s1，输入为(0,0)/(0,1)/(1,0)时，转移到s0

状态图简化表示：

┌──────────────────┐                ┌──────────────────┐
│   s0 (输出0)     │ ◄──────────────│   s1 (输出1)     │
└──────────────────┘                └──────────────────┘
          │ ▲                            │ ▲
          │ │ (0,0),(0,1),(1,0)          │ │ (0,0),(0,1),(1,0)
          │ │                            │ │
(1,1)     │ │                            │ │ (1,1)
──────────► │                            └─┘
          │
          ▼
┌──────────────────┐
│   s1 (输出1)     │
└──────────────────┘

为什么你的初始模型无意义？ #

你之前的模型错误引入了依赖历史的状态转换（比如s0→s2→s3），违背了组合逻辑"无记忆"的核心特性。组合逻辑不需要追踪输入的先后顺序，所有输出仅由当前输入组合决定，因此状态机的设计不能包含依赖历史的状态链。

内容的提问来源于stack exchange，提问作者David542