Zephyr's Notes on ISCS & CBMS, UTokyo

有限状态机

Nov 16, 20247 min read

有限状态机 | Finite State Machine (FSM)

定义 | Definition

有限状态机（FSM）是一种用于建模离散事件系统的数学模型，由有限数量的状态、状态之间的转移和一组事件组成。FSM 可以用来描述一个系统在特定时间点的状态以及事件发生时系统如何从一个状态转移到另一个状态。

A Finite State Machine (FSM) is a mathematical model used to design and describe the behavior of discrete event systems. It consists of a finite number of states, transitions between those states, and a set of events. FSM can describe the state of a system at a specific point in time and how the system transitions from one state to another when events occur.

组成部分 | Components

  1. 状态集 | Set of States ()

    • 有限的状态集合，表示系统可能处于的所有状态。
    • A finite set of states representing all possible states of the system.

  2. 输入符号集 | Set of Input Symbols ()

    • 触发状态转移的事件或输入符号的集合。
    • A set of input symbols that trigger state transitions.

  3. 转移函数 | State Transition Function ()

    • 定义当前状态和输入符号如何决定下一个状态：。
    • A function that defines how the current state and an input symbol determine the next state: .

  4. 初始状态 | Initial State ()

    • 系统开始时的状态。
    • The state where the system starts.

  5. 接受状态集 | Set of Accepting States ()

    • 表示接受输入序列后系统所处的状态集（仅用于确定型有限自动机）。
    • A set of states that denote where the system accepts the input sequence (used in deterministic finite automata).

分类 | Types

确定型有限状态机 (DFA) | Deterministic Finite Automaton (DFA)

  • 定义 | Definition：每个状态和输入符号对都有且仅有一个确定的下一个状态。 Each state and input symbol pair has exactly one determined next state.
  • 形式化 | Formal Representation：。

非确定型有限状态机 (NFA) | Non-deterministic Finite Automaton (NFA)

  • 定义 | Definition：每个状态和输入符号对可以有零个或多个可能的下一个状态。 Each state and input symbol pair can have zero or more possible next states.
  • 形式化 | Formal Representation：。

推动型有限状态机 | Mealy and Moore Machines

  • Mealy 机 | Mealy Machine：输出取决于当前状态和输入符号。 Output depends on the current state and input symbol.
  • Moore 机 | Moore Machine：输出仅取决于当前状态。 Output depends only on the current state.

示例 | Examples

确定型有限状态机 (DFA) 示例 | Example of DFA

假设一个简单的 DFA 用于识别包含偶数个 0 的二进制字符串。

Suppose a simple DFA to recognize binary strings containing an even number of 0s.

状态集 | States: S = {q0, q1}
输入符号集 | Input Symbols: Σ = {0, 1}
初始状态 | Initial State: s0 = q0
接受状态 | Accepting States: F = {q0}
转移函数 | Transition Function:
δ(q0, 0) = q1, δ(q0, 1) = q0
δ(q1, 0) = q0, δ(q1, 1) = q1

状态转移图 | State Transition Diagram

q0 --0--> q1
q0 --1--> q0
q1 --0--> q0
q1 --1--> q1

非确定型有限状态机 (NFA) 示例 | Example of NFA

假设一个简单的 NFA 用于识别包含子串“ab”的字符串。

Suppose a simple NFA to recognize strings containing the substring “ab”.

状态集 | States: S = {q0, q1, q2}
输入符号集 | Input Symbols: Σ = {a, b}
初始状态 | Initial State: s0 = q0
接受状态 | Accepting States: F = {q2}
转移函数 | Transition Function:
δ(q0, a) = {q0, q1}
δ(q0, b) = {q0}
δ(q1, b) = {q2}
δ(q2, a) = {}
δ(q2, b) = {}

状态转移图 | State Transition Diagram

q0 --a--> q1
q0 --a--> q0
q0 --b--> q0
q1 --b--> q2

推动型有限状态机示例 | Example of Mealy and Moore Machines

Mealy 机 | Mealy Machine

假设一个 Mealy 机用于检测输入中的偶数个 1。

Suppose a Mealy machine to detect an even number of 1s in the input.

状态集 | States: S = {q0, q1}
输入符号集 | Input Symbols: Σ = {0, 1}
输出符号集 | Output Symbols: Λ = {E, O}
初始状态 | Initial State: s0 = q0
转移函数 | Transition Function:
δ(q0, 0) = q0, output = E
δ(q0, 1) = q1, output = O
δ(q1, 0) = q1, output = O
δ(q1, 1) = q0, output = E

Moore 机 | Moore Machine

假设一个 Moore 机用于检测输入中的偶数个 1。

Suppose a Moore machine to detect an even number of 1s in the input.

状态集 | States: S = {q0, q1}
输入符号集 | Input Symbols: Σ = {0, 1}
输出符号集 | Output Symbols: Λ = {E, O}
初始状态 | Initial State: s0 = q0
输出函数 | Output Function:
λ(q0) = E
λ(q1) = O
转移函数 | Transition Function:
δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q1
δ(q1, 1) = q0

状态转移图 | State Transition Diagram for Moore Machine

q0 --0--> q0 (E)
q0 --1--> q1 (O)
q1 --0--> q1 (O)
q1 --1--> q0 (E)

应用 | Applications

  1. 编译器设计 | Compiler Design

    • 用于词法分析和语法分析。
    • Used in lexical analysis and syntax analysis.

  2. 控制系统 | Control Systems

    • 用于建模和设计嵌入式系统中的控制逻辑。
    • Used for modeling and designing control logic in embedded systems.

  3. 通信协议 | Communication Protocols

    • 用于定义协议状态和转移。
    • Used for defining protocol states and transitions.

  4. 人工智能 | Artificial Intelligence

    • 用于状态空间搜索和游戏 AI 的状态机设计。
    • Used for state space search and state machine design in game AI.

总结 | Summary

有限状态机是一种强大的建模工具，在计算机科学和工程的多个领域中具有广泛的应用。通过理解其组成部分、工作原理和应用场景，可以有效地设计和分析复杂系统的行为。

Finite state machines are powerful modeling tools widely used in various fields of computer science and engineering. Understanding their components, working principles, and application scenarios allows for effective design and analysis of complex system behaviors.

Graph View

Backlinks