如何根据正规式构造DFA

要根据正则表达式构造DFA，可以按照以下步骤进行：

1.根据正则表达式，使用 Thompson 构造法或者转换法，构造 NFA。

2.将 NFA 转换为 DFA。

3.最小化 DFA，以得到最小的 DFA。

下面以正则表达式 (a|b)*abb 为例来说明具体方法：

1.使用 Thompson 构造法，先将正则表达式转换为 NFA。将正则表达式进行分解，可以得到以下三个子表达式：

(a|b)*
a
b
根据 Thompson 构造法的规则，首先构造 (a|b)* 的 NFA。将 a 和 b 分别作为两个状态，中间添加一个空串转移，然后再添加一个状态作为接受状态。将这个可以匹配 a 或 b 的子表达式构造为一个 NFA，如下图所示。

接下来，构造子表达式 a 和 b 的 NFA。将 a 和 b 分别作为两个状态，中间添加一个标记为 a 或 b 的转移，然后再添加一个状态作为接受状态。将这两个只能匹配 a 或 b 的子表达式构造为两个 NFA，如下图所示。

2.将构造得到的 NFA 转换为 DFA。

将 NFA 转换为 DFA 的过程分为以下几步：

1）从 NFA 的起始状态集合开始，通过 ε-闭包操作得到该起始状态集合的 ε-闭包；

2）接着，对该 ε-闭包中的每个状态，针对每个输入符号做状态转换操作，并将新的状态加入到 DFA 中；

3）用新状态集合取代原状态集合，持续执行 1）和 2），直到无法继续搜索。

根据这个方法，对于 (a|b)*abb，我们可以求出如下的 DFA 图形：

3.最小化 DFA

DFA 已经构造完成，但可能仍不是最小的 DFA。下面使用等价类划分算法对此 DFA 进行最小化。

首先，将状态分为两组：接受状态和非接受状态。每个状态都属于其中一个组。

接下来，对每个非接受状态和每个接受状态分别进行划分。具体方法如下：

1）选取一个状态作为代表元素。

2）对其他状态进行分类：

如果该状态到达的状态集合属于同一组，则将该状态归入该组；

否则，将该状态归入另一组。

重复上述过程，直到无法再进行划分。最终得到的划分就是达到了最小化。最后，将得到的最小化 DFA 重新画图，得到如下的 DFA 图形：