正则表达式转dfa例题

正则表达式是一种用于匹配字符串的表达式，它可以描述某个特定模式的字符串。但是，计算机无法直接使用正则表达式，因此我们需要将其转换为另一种形式，即DFA（确定性有限状态自动机）。本文将以具体的例题为例，从多个角度分析如何将正则表达式转换为DFA。

例题：将正则表达式（a|b)*abb转换为DFA。

1. 正则表达式转NFA

首先，我们需要将正则表达式转换为NFA（非确定性有限状态自动机）。这是因为NFA的转换比DFA更加容易，且可以处理一些DFA无法处理的语言。

将正则表达式（a|b)*abb转换为NFA的过程如下：

① 将正则表达式转换为后缀表达式：ab|*

② 基于后缀表达式构建NFA（图示中的箭头表示空转移）：

0| ε | 1

1| a | 2

1| b | 3

2| ε | 4

3| ε | 4

4| a | 5

5| b | 6

从上图可以看出，该NFA共有6个状态，其中状态6为接受状态。

2. NFA转DFA

接下来，我们将该NFA转换为DFA。该过程包括以下几个步骤：

① 计算NFA的ε闭包，也就是从起始状态出发，可以到达的所有状态，包括经过任意数量的空转移所能到达的状态。我们可以使用子集构造算法（即将NFA的所有状态集合视为一个DFA状态）来计算ε闭包。

初始状态集合：{0}

经过ε转移可以到达的状态：{0,1}

{0,1}经过ε转移可以到达的状态：{0,1,2,3}

{0,1,2,3}经过ε转移可以到达的状态：{0,1,2,3,4}

{0,1,2,3,4}经过ε转移可以到达的状态：{0,1,2,3,4,5}

② 对于每个DFA状态，计算转移函数。假设当前NFA的ε闭包是S，则其对应的DFA状态为T。若从T中任意取出一个状态t，且t经过a转移能够到达状态集合U，则T通过a转移可到达U。我们也可以使用子集构造算法来计算转移函数。

状态0通过a转移可以到达状态集合{2}

状态0通过b转移可以到达状态集合{3}

状态1通过a转移可以到达状态集合{2}

状态1通过b转移可以到达状态集合{3}

状态2通过a转移可以到达状态集合{2,4}

状态2通过b转移无法到达任何状态

状态3通过a转移可以到达状态集合{4}

状态3通过b转移无法到达任何状态

状态4通过a转移可以到达状态集合{5}

状态4通过b转移无法到达任何状态

状态5通过a或b转移均无法到达任何状态，是接受状态。

3. 绘制DFA

基于上述步骤，我们得到了如下DFA：

a | b

----------

▼ | ▼

T1 | T2

▼ | ▼

T2 | T3

▼ | x

T3 | x

▼ | x

T4 | x

▼ | x

T5 | T5

▼ | ▼

x | x

其中T1、T2、T3、T4、T5分别表示由NFA的状态集合{0,1}、{0,1,2,3}、{0,1,2,3,4}、{0,1,2,3,4,5}、{5}生成的DFA状态。

4.