正则表达式转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.
