觉得需要搞一篇啊!
dfa是啥
大家都知道
dfa最小化
dfa应该如何最小化呢。我们都知道，肯定是把状态划分成若干等价类，每个等价类合并成一个，要求每个等价类中的点的后继们对应等价。
考虑我们一开始让接受状态都合并成一个，拒绝状态都合并成一个，然后开始分裂，如果两个状态的同一转移指向不同的等价类，那么它们肯定也不在同一个等价类，需要把它们分裂一下。这称为moore算法。
但是我们可能会分裂$\Omega(n)$轮，比如一条长链，每个位置有两个点，可以构造一下让这些点顺次分裂。所以每次都检查是$O(n^2\Sigma)$的。
考虑维护一个队列，哪个等价类分裂了就把分裂出来的放进去，然后去检查那些到它有转移的等价类。比如现在我们从队列里拿出$T$，枚举了一个字符$c$，如果一个等价类$S$，其中有的点的转移$c$连向$T$，那么我们就需要把$S$分裂成连向$T$和不连向$T$的两部分，这里需要用链表来让分裂的复杂度只和连向$T$的点数有关。
关键的一步是，当我们分裂出两个等价类时，只把较小的那个放进队列里，容易发现这样不影响正确性。这样一个点只会参与$\log$次作为$T$，所以复杂度是$O(n\Sigma\log n)$。这里队列也没有必要是队列。这称为hopcroft算法。
有趣的是两个算法随机数据下都是$O(n(\Sigma+\log n))$的，不过当然还是hopcroft要快一些。
我尝试写一个板子。没有经过测试。据说std::slist可能不是很快，这里可以vector懒删除或者手写链表，看起来后者简单一些。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const int S=26;
struct DFA
{
vector<int> b;
vector<array<int,S> > e;
inline void minimize()
{
vector<slist<int> > v(2);
vector<slist<int>::iterator> it(e.size());
vector<int> p(e.size()),q(e.size());
vector<array<vector<int>,S> > re(e.size());
for(int i=0;i<e.size();i++) v[b[i]].push_back(i);
for(int i=0;i<e.size();i++)
for(int c=0;c<S;c++) re[e[i][c]][c].push_back(i);
queue<pair<int,int> > q;
q.push({0,v[0].size()}),q.push({1,v[1].size()});
while(!q.empty())
{
pair<int,int> now=q.front();q.pop();
int i=now.first;
if(v[i].size()!=now.second) continue;
for(int c=0;c<S;c++)
{
for(int u:v[i])
for(int w:re[u][c])
!q[p[w]]&&(t.push_back(p[w]),q[p[w]]=v.size(),v.push_back({}),0),
v[p[w]].erase(it[w]),v[q[p[w]]].push_front(w),it[w]=v[q[p[w]]].begin();
int t;
for(int u:v[i])
for(int w:re[u][c])
if(!vis[p[w]]) t=(v[p[w]].size()<v[q[p[w]]].size()?p[w]:q[p[w]]),q.push({t,v[t].size()}),vis[p[w]]=1;
for(int u:v[i])
for(int w:re[u][c]) vis[p[w]]=q[p[w]]=0;
}
}
}
}
笛卡尔积
比如我们要给两个dfa求交/并/对称差，怎么办呢，可以建一个新的dfa，状态是它俩的笛卡尔积，如果在第一个dfa上$x_1\stackrel{c}{\rightarrow} y_1$，第二个$x_2\stackrel{c}{\rightarrow} y_2$，那么笛卡尔积上连$(x_1,x_2)\stackrel{c}{\rightarrow} (y_1,y_2)$。然后什么样的状态是接受状态是显然的。最后对它最小化即可。
遗憾的是笛卡尔积最小化后的大小最坏情况下就是两边大小的乘积。
来自vuq的题
图，每个点有红蓝两条出边和黑白之一的颜色，求从$x,y$两个点开始，每次让两个点同时沿某个颜色的出边移动一步，最少多少步可以让两个点颜色不同。$n\leq 10^5$。
相当于分别以$x,y$为初始状态看成一个dfa，然后求它俩对称差接受的最短的串。但是这是$n^2$的啊?
需要一点转化。直接对它跑moore dfa最小化，我们断言答案就是$x,y$被分裂到不同等价类时的轮数。考虑分裂时发生了什么，第$k$轮两个点不等价，当且仅当两个点通过一次相同的转移可以走到第$k-1$轮不等价的两个点，也就是通过$k$次相同的转移可以走到颜色不同的两个点。
也可以使用hopcroft，额外记一下每个点被分裂出时应该是第几轮，每次取出最小的进行分裂即可。可以处理任意字符集任意颜色数多组询问的情况，复杂度$O(n\Sigma\log n)$。
等价判定
如何判断两个dfa是不是等价呢。直接最小化后按字典序dfs，dfn相等的点必然是对应的。
Černý定理
如果任意状态在经过一个串的转移之后都到达同一个状态，那么称它是同步的。如果这个状态是初始状态，它是重置的。
一个dfa存在同步串，当且仅当任意两个状态都可以被一个串同步。这是显然的，因为当两个串同步之后，接下来它们可以进行相同的转移。那么这就转化成计算dfa交是否为空了。
这个证明是比较经典的，类似的trick出现在xxvi poi stage 2 Zjazd obieżyświatów，joisc 忘了哪年 Sparklers，unr 2022 面基之路，等等。
置换
一个dfa是置换的，当且仅当单看每个字符，转移形成若干个环。
我们可以用$O(\sqrt{n})$个状态的置换dfa区别任何两个串。这个构造在 http://www.numdam.org/item/?id=ITA_1996__30_1_81_0 ，如果你有空可以拿它出个板子题。
对于一般dfa，目前最好的界是$O(n^\frac{2}{5}\log^\frac{3}{5}n)$。