有限状态自动机

确定性有限状态自动机 DFA

DFA Definition

DFA 是一个五元组 $(Q,\Sigma, \delta,q_0,F)$ :

有限状态集合 $Q$ .
如果把 DFA 看作一张有向图，那么 $Q$ 中的每一个状态可以看作是节点.
字符集 $\Sigma$
DFA 只能接受字符集中的字符输入.
转移函数 $\delta:Q\times \Sigma\mapsto Q$
类似于有向图中的有向边.
起始状态 $q_0$
接受状态集合 $F$ . 表示哪些状态是可以接受的. 满足 $F\subseteq Q$

模板代码

struct DFA {
    int m; // 字符集大小
    int n; // 状态数量
    int q0; // 初始状态
    std::vector<std::vector<int>> trans; // 状态转移
    std::vector<int> acc; // 接受状态

    DFA(int m, int n = 0, int q0 = 0): 
        m{m}, n{n}, q0{q0}, trans(m, std::vector<int>(n)), acc(n) {}

    // 使用 Hopcroft 算法返回的自动机最小化.
    DFA minimize() const;
};