C++ 有限状态自动机（FSM）：原理、实现与应用全解析

Ne0inhk

— 15 min read
C++ 有限状态自动机（FSM）：原理、实现与应用全解析
在这里插入图片描述

标题

C++ 有限状态自动机（FSM）：原理、实现与应用全解析

有限状态自动机（Finite State Machine, FSM，也叫有限状态机）是一种抽象计算模型，核心思想是将复杂的逻辑拆解为「状态」和「状态转移」，通过输入触发状态变化，最终完成特定逻辑处理。它广泛应用于编译器、协议解析、文本处理、游戏AI等场景，也是实现AC自动机、KMP等算法的底层思想。本文将从核心原理、分类、C++实现模式到实战案例，全面解析有限状态自动机的设计与落地技巧。

一、有限状态自动机的核心背景与定义

1.1 问题引入：复杂逻辑的结构化拆解

面对需要根据“上下文/历史输入”做决策的场景（如解析JSON、验证手机号、处理TCP协议），纯分支判断（if-else/switch）会导致代码臃肿、可读性差、易出错：

// 反面例子：用switch验证手机号（仅11位数字，以1开头）boolvalidatePhone(const string& s){if(s.size()!=11)returnfalse;for(int i =0; i < s.size();++i){switch(i){case0:if(s[i]!='1')returnfalse;break;default:if(!isdigit(s[i]))returnfalse;break;}}returntrue;}

这种写法在规则复杂时（如支持带区号、分机号的手机号）会迅速失控。

有限状态自动机的核心价值：

  • 结构化：将逻辑拆分为「状态」「输入」「转移规则」，代码可维护性大幅提升；
  • 可扩展：新增规则只需添加状态/转移，无需修改核心逻辑；
  • 可验证：状态机的逻辑可通过画图/数学方法验证正确性。

1.2 核心概念定义

一个有限状态自动机由 5 个核心元素组成（五元组）：

  1. 状态集合（S）：所有可能的状态，包含：
    • 初始状态（Start State）：自动机的起始点；
    • 终止状态（Accept State）：表示逻辑完成/验证通过的状态；
    • 中间状态：处理输入的过渡状态。
  2. 输入字母表（Σ）：所有可能的输入类型（如数字、字母、特定字符）。
  3. 转移函数（δ）：δ(current_state, input) → next_state，定义“当前状态+输入”对应的下一个状态。
  4. 初始状态（s₀）：属于 S，自动机的起点。
  5. 终止状态集合（F）：F ⊆ S，代表逻辑完成的状态。

分类：

  • 确定性有限状态自动机（DFA）：每个状态+输入对应唯一的下一个状态（实战中最常用）；
  • 非确定性有限状态自动机（NFA）：每个状态+输入对应多个下一个状态，可通过子集构造法转为DFA。

示例：验证“11位手机号（以1开头，后10位为数字）”的DFA：

  • 状态集合 S：{初始态S0, 数字态S1, 终止态S2, 错误态S3}；
  • 输入字母表 Σ：{数字字符（0-9）}；
  • 转移函数：
    • δ(S0, ‘1’) → S1；δ(S0, 非’1’) → S3；
    • δ(S1, 数字) → S1（累计9次后）→ S2；δ(S1, 非数字) → S3；
    • δ(S2, 任意) → S3；δ(S3, 任意) → S3；
  • 初始状态 s₀：S0；
  • 终止状态 F：{S2}。

二、有限状态自动机的C++实现模式

有限状态自动机的实现有多种模式，从简单到复杂依次为：表驱动型、状态对象型、函数指针/回调型，其中表驱动型是实战中最常用的方式。

2.1 模式1：表驱动型DFA（最简洁，适合简单逻辑）

核心思想：用二维数组/哈希表存储转移规则，通过查表实现状态转移，代码结构清晰、易扩展。

实现步骤：
  1. 定义状态枚举；
  2. 定义转移表（状态×输入→下一个状态）；
  3. 实现输入处理逻辑，遍历输入并查表转移状态；
  4. 最终判断是否处于终止状态。
完整实现（验证11位手机号）：
#include<iostream>#include<string>#include<unordered_map>usingnamespace std;// 步骤1：定义状态枚举enumState{ S0,// 初始状态：等待输入第一位（必须是1） S1,// 中间状态：已输入1位，还需输入10位数字 S2,// 终止状态：已输入11位有效手机号 S3 // 错误状态：输入无效};// 步骤2：定义输入类型（简化：仅区分'1'、其他数字、非数字）enumInputType{ INPUT_1,// 字符'1' INPUT_DIGIT,// 其他数字（0,2-9） INPUT_OTHER // 非数字字符};// 辅助函数：将输入字符转为InputType InputType getInputType(char c){if(!isdigit(c))return INPUT_OTHER;if(c =='1')return INPUT_1;return INPUT_DIGIT;}intmain(){// 步骤3：构建转移表（二维数组：当前状态 × 输入类型 → 下一个状态） State transition_table[4][3]={// S0的转移：INPUT_1→S1，INPUT_DIGIT→S3，INPUT_OTHER→S3{S1, S3, S3},// S1的转移：需累计输入10位数字后到S2，否则保持S1；非数字到S3{S1, S1, S3},// S2的转移：任意输入到S3{S3, S3, S3},// S3的转移：任意输入保持S3{S3, S3, S3}};// 测试用例 vector<string> test_cases ={"13800138000","1234567890","23800138000","1380013800a"};for(const string& phone : test_cases){ State current_state = S0;int digit_count =0;// 记录S1状态下输入的数字数// 步骤4：遍历输入，执行状态转移for(char c : phone){ InputType input =getInputType(c); current_state = transition_table[current_state][input];// 处理S1的特殊逻辑：累计数字数到10则转为S2if(current_state == S1){ digit_count++;if(digit_count ==10){ current_state = S2;}}// 错误状态直接终止if(current_state == S3)break;}// 步骤5：判断是否处于终止状态bool valid =(current_state == S2); cout <<"手机号："<< phone <<" → "<<(valid ?"有效":"无效")<< endl;}return0;}

输出结果：

手机号：13800138000 → 有效 手机号：1234567890 → 无效 手机号：23800138000 → 无效 手机号：1380013800a → 无效

2.2 模式2：状态对象型DFA（面向对象，适合复杂逻辑）

核心思想：将每个状态封装为类/对象，状态转移由对象自身处理，符合开闭原则（新增状态无需修改原有代码）。

完整实现（解析简单的键值对：key=value）：
#include<iostream>#include<string>#include<memory>usingnamespace std;// 前向声明状态基类classState;// 上下文类：存储自动机的状态、输入、结果等信息classContext{public: string input;// 输入字符串int pos;// 当前处理位置 string key;// 解析出的key string value;// 解析出的valuebool is_valid;// 是否解析成功 shared_ptr<State> current_state;// 当前状态Context(const string& in):input(in),pos(0),is_valid(false){}// 切换状态voidsetState(shared_ptr<State> state){ current_state = state;}// 获取当前输入字符（越界返回'\0'）chargetCurrentChar(){return(pos < input.size())? input[pos]:'\0';}// 移动到下一个字符voidnextChar(){if(pos < input.size()) pos++;}};// 状态基类（抽象类）classState{public:virtual~State()=default;// 处理当前输入，返回下一个状态virtualvoidhandle(Context& ctx)=0;};// 初始状态：等待输入key的第一个字符classStartState:publicState{public:voidhandle(Context& ctx)override{char c = ctx.getCurrentChar();if(c =='\0'){// 空输入 ctx.is_valid =false;return;}if(isalnum(c)){// 字母/数字：加入key，切换到KeyState ctx.key += c; ctx.nextChar(); ctx.setState(make_shared<KeyState>());}else{// 无效字符 ctx.is_valid =false;}}};// Key状态：继续输入key，直到遇到'='classKeyState:publicState{public:voidhandle(Context& ctx)override{char c = ctx.getCurrentChar();if(c =='='){// 遇到等号：切换到ValueState ctx.nextChar(); ctx.setState(make_shared<ValueState>());}elseif(isalnum(c)){// 字母/数字：继续加入key ctx.key += c; ctx.nextChar();}else{// 无效字符 ctx.is_valid =false;}}};// Value状态：输入value，直到结束classValueState:publicState{public:voidhandle(Context& ctx)override{char c = ctx.getCurrentChar();if(c =='\0'){// 输入结束：验证通过 ctx.is_valid =!ctx.value.empty();return;}if(isalnum(c)){// 字母/数字：加入value ctx.value += c; ctx.nextChar();}else{// 无效字符 ctx.is_valid =false;}}};// 有限状态自动机类classKeyValueParser{private: Context ctx;public:KeyValueParser(const string& input):ctx(input){// 初始状态为StartState ctx.setState(make_shared<StartState>());}// 执行解析boolparse(){while(ctx.current_state && ctx.is_valid !=false){ ctx.current_state->handle(ctx);// 输入处理完毕则退出if(ctx.getCurrentChar()=='\0')break;}return ctx.is_valid;}// 获取解析结果 pair<string, string>getResult(){return{ctx.key, ctx.value};}};// 测试代码intmain(){ vector<string> test_cases ={"name=alice","age=20","id=12345","invalid=123#","empty="};for(const string& s : test_cases){ KeyValueParser parser(s);bool success = parser.parse();auto[key, value]= parser.getResult(); cout <<"输入："<< s <<" → "<<(success ?"解析成功":"解析失败");if(success){ cout <<" (key="<< key <<", value="<< value <<")";} cout << endl;}return0;}

输出结果：

输入：name=alice → 解析成功 (key=name, value=alice) 输入：age=20 → 解析成功 (key=age, value=20) 输入：id=12345 → 解析成功 (key=id, value=12345) 输入：invalid=123# → 解析失败 输入：empty= → 解析失败

2.3 模式3：函数指针/回调型（灵活，适合高性能场景）

核心思想：用函数指针/std::function 代替状态类，减少对象创建开销，适合高性能、简单状态机场景。

#include<iostream>#include<string>#include<functional>usingnamespace std;// 上下文结构体structFSMContext{ string input;int pos;bool is_valid;// 状态转移函数类型：Context → 下一个状态函数using StateFunc = function<void(FSMContext&)>; StateFunc current_state;FSMContext(const string& in):input(in),pos(0),is_valid(true){}};// 状态函数：初始状态（验证是否为数字）voidstate_start(FSMContext& ctx){if(ctx.pos >= ctx.input.size()){ ctx.is_valid =false;return;}char c = ctx.input[ctx.pos];if(isdigit(c)){ ctx.pos++; ctx.current_state =[](FSMContext& ctx){state_digit(ctx);};}else{ ctx.is_valid =false;}}// 状态函数：数字状态（持续验证数字）voidstate_digit(FSMContext& ctx){if(ctx.pos >= ctx.input.size()){// 输入结束，验证通过return;}char c = ctx.input[ctx.pos];if(isdigit(c)){ ctx.pos++;}else{ ctx.is_valid =false;}}// 测试：验证纯数字字符串boolvalidateNumber(const string& s){ FSMContext ctx(s); ctx.current_state = state_start;while(ctx.current_state && ctx.is_valid){ ctx.current_state(ctx);// 输入处理完毕则退出if(ctx.pos >= s.size())break;}return ctx.is_valid;}intmain(){ cout << boolalpha; cout <<validateNumber("12345")<< endl;// true cout <<validateNumber("123a5")<< endl;// false cout <<validateNumber("")<< endl;// falsereturn0;}

三、有限状态自动机的实战应用

3.1 应用1：文本分词（简单关键词提取）

实现一个分词器，提取文本中的“数字”“字母”“标点”三类token：

enumTokenType{ TOKEN_DIGIT, TOKEN_ALPHA, TOKEN_PUNCT, TOKEN_EOF };enumState{ S_INIT, S_DIGIT, S_ALPHA, S_PUNCT };structToken{ TokenType type; string value;}; vector<Token>tokenize(const string& text){ vector<Token> tokens; State current_state = S_INIT; string current_token;auto flush_token =[&](TokenType type){if(!current_token.empty()){ tokens.push_back({type, current_token}); current_token.clear();}};for(char c : text){switch(current_state){case S_INIT:if(isdigit(c)){ current_token += c; current_state = S_DIGIT;}elseif(isalpha(c)){ current_token += c; current_state = S_ALPHA;}elseif(ispunct(c)){ current_token += c; current_state = S_PUNCT;}break;case S_DIGIT:if(isdigit(c)){ current_token += c;}else{flush_token(TOKEN_DIGIT); current_state = S_INIT;// 回退字符，重新处理if(isalpha(c)||ispunct(c)){// 重新处理当前字符 current_token += c; current_state =isalpha(c)? S_ALPHA : S_PUNCT;}}break;case S_ALPHA:if(isalpha(c)){ current_token += c;}else{flush_token(TOKEN_ALPHA); current_state = S_INIT;if(isdigit(c)||ispunct(c)){ current_token += c; current_state =isdigit(c)? S_DIGIT : S_PUNCT;}}break;case S_PUNCT:flush_token(TOKEN_PUNCT); current_state = S_INIT;if(isdigit(c)||isalpha(c)){ current_token += c; current_state =isdigit(c)? S_DIGIT : S_ALPHA;}break;}}// 处理最后一个tokenif(current_state == S_DIGIT)flush_token(TOKEN_DIGIT);elseif(current_state == S_ALPHA)flush_token(TOKEN_ALPHA);elseif(current_state == S_PUNCT)flush_token(TOKEN_PUNCT); tokens.push_back({TOKEN_EOF,""});return tokens;}// 测试intmain(){ string text ="hello123,world456!";auto tokens =tokenize(text);for(constauto& token : tokens){ string type_str;switch(token.type){case TOKEN_DIGIT: type_str ="数字";break;case TOKEN_ALPHA: type_str ="字母";break;case TOKEN_PUNCT: type_str ="标点";break;case TOKEN_EOF: type_str ="结束";break;} cout << type_str <<": "<< token.value << endl;}return0;}

3.2 应用2：实现简单的正则表达式匹配（匹配ab*c）

匹配规则：以a开头，后跟任意个b，最后以c结尾（如ac、abc、abbbc均匹配）：

boolmatchAbc(const string& s){enumState{ S0, S1, S2, S3 }; State current = S0;for(char c : s){switch(current){case S0:// 初始态：等待aif(c =='a') current = S1;elsereturnfalse;break;case S1:// 已匹配a，等待b或cif(c =='b') current = S1;// 继续匹配belseif(c =='c') current = S2;// 匹配到c，进入终止态elsereturnfalse;break;case S2:// 终止态：后续字符无效returnfalse;case S3:// 错误态returnfalse;}}// 最终必须处于S2（已匹配c）return current == S2;}// 测试intmain(){ cout << boolalpha; cout <<matchAbc("ac")<< endl;// true cout <<matchAbc("abc")<< endl;// true cout <<matchAbc("abbbc")<< endl;// true cout <<matchAbc("abx")<< endl;// false cout <<matchAbc("a")<< endl;// falsereturn0;}

3.3 应用3：协议解析（模拟TCP握手状态机）

模拟TCP三次握手的状态转移：CLOSED → SYN_SENT → SYN_RECV → ESTABLISHED：

enumTCPState{ CLOSED, SYN_SENT, SYN_RECV, ESTABLISHED };enumTCPEvent{ EV_SYN, EV_SYN_ACK, EV_ACK };// 转移函数 TCPState tcpTransition(TCPState current, TCPEvent event){switch(current){case CLOSED:return(event == EV_SYN)? SYN_SENT : CLOSED;case SYN_SENT:return(event == EV_SYN_ACK)? SYN_RECV : SYN_SENT;case SYN_RECV:return(event == EV_ACK)? ESTABLISHED : SYN_RECV;case ESTABLISHED:return ESTABLISHED;default:return CLOSED;}}// 测试三次握手intmain(){ TCPState state = CLOSED;// 事件序列：SYN → SYN_ACK → ACK vector<TCPEvent> events ={EV_SYN, EV_SYN_ACK, EV_ACK};for(auto event : events){ state =tcpTransition(state, event); cout <<"当前状态：";switch(state){case CLOSED: cout <<"CLOSED";break;case SYN_SENT: cout <<"SYN_SENT";break;case SYN_RECV: cout <<"SYN_RECV";break;case ESTABLISHED: cout <<"ESTABLISHED";break;} cout << endl;}// 最终状态应为ESTABLISHED cout <<"握手是否成功："<<(state == ESTABLISHED)<< endl;return0;}

四、有限状态自动机的优化与注意事项

4.1 优化技巧

  1. 状态合并：将逻辑等价的状态合并，减少状态数量（如所有错误态可合并为一个）；
  2. 输入分类：将相似输入合并为同一类型（如所有数字归为INPUT_DIGIT），简化转移表；
  3. 预编译转移表：对于固定规则的DFA，可在编译期生成转移表（如用constexpr），提升运行效率；
  4. 惰性处理：对于长输入，可边读取边处理，无需一次性加载所有输入。

4.2 常见错误

  1. 遗漏终止状态判断：仅处理完输入但未检查是否处于终止态（如手机号验证到10位就返回，未到11位）；
  2. 状态转移不全：未覆盖所有“状态+输入”组合，导致空指针/未定义行为；
  3. 错误态未处理：进入错误态后仍继续处理输入，导致逻辑错误；
  4. 初始状态错误：未正确设置初始状态，导致整个自动机逻辑错误。

4.3 DFA vs NFA

  • DFA：实现简单、效率高（每个输入仅一次状态转移），适合大部分实战场景；
  • NFA：表达能力更强（支持正则表达式的|、*、+等），但实现复杂，通常先转为DFA再使用。

五、总结

有限状态自动机是处理“基于上下文的输入处理”的核心工具，核心要点可总结为：

  1. 核心思想：将复杂逻辑拆解为「状态」和「状态转移」，通过输入触发状态变化，最终到达终止态；
  2. 实现模式：
    • 表驱动型：简洁易维护，适合简单规则（如验证、简单解析）；
    • 状态对象型：面向对象，易扩展，适合复杂规则（如协议解析、分词）；
    • 函数指针型：高性能，适合简单、高频调用的场景；
  3. 核心优势：结构化、可扩展、可验证，避免冗长的if-else/switch；
  4. 应用场景：文本验证、协议解析、分词、正则匹配、游戏AI、编译器前端等。

掌握有限状态自动机的关键：

  • 先通过画图明确状态、输入、转移规则（可视化是理解的关键）；
  • 优先选择表驱动型实现（简单场景），复杂场景再用状态对象型；
  • 务必覆盖所有“状态+输入”组合，避免逻辑漏洞。

有限状态自动机是AC自动机、KMP等字符串算法的底层思想，理解它能帮助你更深入地掌握这些高级算法，也是C++开发者处理复杂逻辑的必备工具。

Read more

Rust异步编程的错误处理艺术

Rust异步编程的错误处理艺术

Rust异步编程的错误处理艺术 一、异步错误的本质与分类 1.1 异步错误与同步错误的区别 💡在Rust同步编程中，错误通常是通过Result<T, E>类型返回的，Err变体包含了错误信息，程序会阻塞线程直到操作完成。而在异步编程中，操作的结果是一个Future<Output = Result<T, E>>，程序会暂停任务直到操作完成，Err变体可能是IO错误、超时错误、取消错误等异步场景特有的错误。 同步错误示例： usestd::fs::File;usestd::io::Read;// 同步读取文件，阻塞线程fnread_file_sync()->Result<String,std::io::Error>{letmut

By Ne0inhk
【MySQL数据库基础】（二）MySQL 数据库基础从入门到上手，一篇带你吃透核心知识点！

【MySQL数据库基础】（二）MySQL 数据库基础从入门到上手，一篇带你吃透核心知识点！

目录 前言 一、为什么需要数据库？文件存储的痛点全解析 二、主流数据库大盘点，MySQL 的适用场景是什么？ 2.1 主流数据库特性对比 2.2 MySQL 的核心优势 三、MySQL 基础操作，从安装到数据 CRUD 手把手教 3.1 MySQL 的多平台安装方式 3.2 连接 MySQL 服务器，核心指令解析 指令参数详解 简化连接方式 连接成功的反馈 3.3 MySQL 服务器管理（Windows 平台） 3.4 服务器、数据库、表的层级关系 3.5 MySQL 核心

By Ne0inhk

ESP8266 Web配网+MQTT+STM32串口上云+免AT指令

本文详细讲解 ESP8266/ESP12F Web 配网、MQTT 通信、STM32/Arduino 串口透传一体化实现方案WiFi强制入户，连接自动打开网页配置，核心亮点是单片机免 ESP8266 AT 指令，串口直接上云，通过串口向 ESP8266 发送数据即可自动上传至 MQTT 服务器，固件开源可直接用于学习调试。 固件下载： 通过网盘分享的文件：mqtt_usart_wifi.ino.bin 链接: https://pan.baidu.com/s/1mZt5diatyYvnSZ-N1eF75w?pwd=e8we 提取码: e8we 免AT指令全网首发！数据直接上传MQTT、秒下发指令，无需复杂配置！下载固件即可使用 一、项目背景与开发初衷         在物联网设备开发过程中，配网和远程通信是两个核心痛点：传统的

By Ne0inhk

4.2_WEB——前端语言三剑客（HTML、JS、CSS）

前言：本文只对三种前端常用的编辑于言 HTML、JS、CSS 的语法做最基础的描述。 一.HTML(Hyper Text Markup Language) 1.概念 * HTML的全称为超文本标记语言，是一种标记语言。它包括一系列标签，通过这些标签可以将网络上的文档格式统一，使分散的Internet资源连接为一个逻辑整体。 * 超文本是一种组织信息的方式，它通过超级链接方法将文本中的文字、图表与其他信息媒体相关联。这些相互关联的信息媒体可能在同一文本中，也可能是其他文件，或是地理位置相距遥远的某台计算机上的文件。 * HTML是一种基础技术，常与CSS、JavaScript一起被众多网站用于设计网页、网页应用程序以及移动应用程序的用户界面 。网页浏览器可以读取HTML文件，并将其渲染成可视化网页。HTML描述了一个网站的结构语义随着线索的呈现，使之成为一种标记语言而非编程语言。 2.特点 超文本标记语言文档制作不是很复杂，但功能强大，支持不同数据格式的文件镶入，这也是万维网（WWW）盛行的原因之一，其主要特点如下： 1. 简易性： 2. 超文本标记语言版本升级采

By Ne0inhk