考虑这样一个问题：为r = (a|b)*abb构造一个DFA。
  对于正则表达式构造DFA的问题：第一步，为正则表达式构造一个NFA；第二步，由NFA转换为DFA表达式。

一、正则表达式构造NFA

参考：《编译原理》龙书，p102。

step 1: 由正则表达式构建语法树

  r = (a|b)*abb

step 2: 为各子式构造NFA

1.2.1 对于r1和r2构造NFA

1.2.2 对r1和r2使用并运算得到r3

1.2.3 对r6、r8、r10构造NFA

1.2.4 对r6、r8、r10使用连接运算

1.2.5 连接2和4中的两部分

二、NFA构造DFA

  r = (a|b)*abb
  在第一节中，我们已经得到了r对应的NFA，下面我们通过NFA来构造DFA。

step 1: 求得start等价开始状态集合

    从状态0可以通过Epsilon到达的状态有{0, 1, 2, 4, 7}，这里包含了本身0状态，记作A = {0, 1, 2, 4, 7}，A为NFA的起始状态集合。

step 2: 寻找标记符号

    这里的输入有{a, b}两种，所以使用a和b来标记NFA状态集合。

step 3: 标记状态集合

2.3.1 使用{a, b}标记A

\begin{align}
Dtran[A, a] &= Epsilon-Closure(move(A, a))\newline
&= Epsilon-Closure({3, 8})\newline
&= {1, 2, 3, 4, 6, 7, 8} = B\newline
&B这里包含了本身{3, 8}状态，下同。
\end{align}

\begin{align}
Dtran[A, b] &= Epsilon-Closure(move(A, b))\newline
&= Epsilon-Closure({5})\newline
&= {1, 4, 5, 6, 7} = C
\end{align}
     Dtran[A, a]表示从DFA状态A可以到达的DFA状态。move(A, a)表示从状态A可以到达的点（NFA状态），本例中是{3, 8}。Epsilon-Closure({3, 8})在本例中表示从{3, 8}藉由a和Epsilon可以到达的点的集合。

2.3.2 使用{a, b}标记B、C

\begin{align}
Dtran[B, a] &= Epsilon-Closure(move(B, a))\newline
&= Epsilon-Closure({3, 8})\newline
&= {1, 2, 3, 4, 6, 7, 8} = B
\end{align}
\begin{align}
Dtran[B, b] &= Epsilon-Closure(move(B, b))\newline
&= Epsilon-Closure({5, 9})\newline
&= {1, 2, 4, 5, 6, 7, 9} = D
\end{align}
\begin{align}
Dtran[C, a] &= Epsilon-Closure(move(C, a))\newline
&= Epsilon-Closure({3, 8})\newline
&= {1, 2, 3, 4, 6, 7, 8} = B
\end{align}
\begin{align}
Dtran[C, b] &= Epsilon-Closure(move(C, b))\newline
&= Epsilon-Closure({5})\newline
&= {1, 4, 5, 6, 7} = C
\end{align}

2.3.3 使用{a, b}标记D

\begin{align}
Dtran[D, a] &= Epsilon-Closure(move(D, a))\newline
&= Epsilon-Closure({3, 8})\newline
&= {1, 2, 3, 4, 6, 7, 8} = B
\end{align}
\begin{align}
Dtran[D, b] &= Epsilon-Closure(move(D, b))\newline
&= Epsilon-Closure({5, 10})\newline
&= {1, 2, 4, 5, 6, 7, 10} = E
\end{align}

2.3.4 使用{a, b}标记E

\begin{align}
Dtran[E, a] &= Epsilon-Closure(move(E, a))\newline
&= Epsilon-Closure({3, 8})\newline
&= {1, 2, 3, 4, 6, 7, 8} = B
\end{align}
\begin{align}
Dtran[E, b] &= Epsilon-Closure(move(E, b))\newline
&= Epsilon-Closure({5})\newline
&= {1, 4, 5, 6, 7} = C
\end{align}

step 4: 状态全部被标记，可列表

NFA状态集合	DFA状态	通过a到达的DFA	通过b到达的DFA
{0, 1, 2, 4, 7}	A	B	C
{1, 2, 3, 4, 6, 7, 8}	B	B	D
{1, 4, 5, 6, 7}	C	B	C
{1, 2, 4, 5, 6, 7, 9}	D	B	E
{1, 2, 4, 5, 6, 7, 10}	E	B	C

step 5: 根据表画图

    我懒得画了。