编译原理 01 正则表达式构造NFA && NFA构造DFA

发布于 2021-06-07  5 次阅读



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

一、正则表达式构造NFA

参考:《编译原理》龙书,p102。

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

  r = (a|b)*abb

图1
图1:语法树

step 2: 为各子式构造NFA

1.2.1 对于r1和r2构造NFA

图2
图2:为r1、r2构造NFA

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

图3
图3:r3的NFA

1.2.3 对r6、r8、r10构造NFA

图4
图4:r6、r8、r10的NFA

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

图5
图5:连接运算

1.2.5 连接2和4中的两部分

图6
图6:最终得到的NFA

二、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: 根据表画图

    我懒得画了。