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++开发者处理复杂逻辑的必备工具。

Could not load content