c++正则表达式转化为dfa

正则表达式转化为DFA的过程可以分为以下几步：

1. 将正则表达式转化为NFA（非确定性有限状态自动机）。

2. 将NFA转化为DFA（确定性有限状态自动机）。

3. 对DFA进行最小化，去除无用状态。

具体步骤如下：

1. 将正则表达式转化为NFA

首先，将正则表达式转化为后缀表达式（也叫逆波兰表达式），然后构建NFA。

例如，对于正则表达式 a*|b，其后缀表达式为 a* b |。构建NFA的过程如下：

1）对于每个字符，创建一个状态，并在该状态上添加一个转移，转移到下一个字符状态。

2）对于每个 *，创建两个状态，分别表示该字符可以出现 0 次或多次。在这两个状态之间添加一个 ε 转移。

3）对于每个 |，创建两个新状态，分别表示两条路径。在这两个状态之间添加一个 ε 转移。

最终得到的NFA如下图所示：


2. 将NFA转化为DFA

在将NFA转化为DFA之前，需要先了解一下 ε-闭包和 ε-转移。

ε-闭包：从一个状态开始，通过 ε 转移可以到达的所有状态的集合。

例如，对于上图中的状态 1，其 ε-闭包为 {1,2,4}。

ε-转移：从当前状态通过 ε 转移可以到达的所有状态。

例如，对于上图中的状态 1，在读入字符 a 后可以到达的状态为 {1,2,4}，其 ε-转移为 {2,4}。

接下来，对于每个状态，找出它的 ε-闭包和从该状态出发读入字符后可以到达的状态，然后将这些状态合并为一个新的 DFA 状态。

例如，对于上图中的 NFA，可以得到以下 DFA：


3. 对DFA进行最小化

最小化 DFA 的目的是去除无用状态，减少状态数目。最小化 DFA 的过程可以使用 Hopcroft 算法或 Moore 算法等。

最终得到的最小化 DFA 如下图所示：


至此，正则表达式转化为 DFA 的过程就完成了。