编译原理 | 从 NFA 到 DFA 的转换（非子集法）

词法分析：从 NFA 到 DFA 的转换

解题方法

1. 写出 K’

K’ 是 K 的全部子集，其中空集 Ø 可以剔除掉（即 K’ 为 K 的幂集）。注意这里 { } 要换成 [ ]。

2. 求 VT’

$V_{T^{\prime }}=V_T$VT′​=VT​

3. 求 S’

$S^{\prime }=\left[S\right]$S′=[S]

4. 求 M’

$M^{\prime }\left(\right[S_1,S_2,\dots ,S_i],a)=[R_1,R_2,\dots ,R_j]a\in V_T$M′([S1​,S2​,… ,Si​],a)=[R1​,R2​,… ,Rj​]a∈VT​

看上去有点复杂，好像看不懂。没关系，看下面例题就懂了。

5. 求 Z’

$Z^{\prime }=\left\{\right[S_1,S_2,...,S_n\left]\mid \right[S_1,S_2,\dots ,S_n]\in K^{\prime }且\{S_1,S_2,\dots ,S_n\}\cap Z\ne \varnothing \}$Z′={[S1​,S2​,...,Sn​]∣[S1​,S2​,… ,Sn​]∈K′且{S1​,S2​,… ,Sn​}∩ Z̸​= ∅ }

看上面公式很复杂，其实就是求 K’ 中含有 Z 的集合。

6. 改写

把 M’ 中的状态重命名一下，改写一下，画出 (DFA)M’ 的状态转换图。

例题

设 (NFA) M = ( {A, B}, {a, b}, M, {A}, {B} ) ，其中 M 定义如下：M (A, a) = {A, B} M (A, b) = {B} M (B, a) = ø M (B, b) = {A, B} 请构造相应确定有穷自动机 (DFA) M’。

解：

1. 写出 K’

K’ 的元素是 [A] [B] [A, B]

2. 求 VT’

$V_{T^{\prime }}=\{a,b\}$VT′​={a,b}

3. 求 S’

$S^{\prime }=\left[A\right]$S′=[A]

4. 求 M’

由于 M（A, a）={A, B}，故有 M’（[A], a）=[A, B]

同样 M’（[A]，b）=[B]

M’（[B]，a）= ø

M’（[B]，b）=[A，B]

由于 M（{A，B}，a）= M（A，a）U M（B，a）= {A，B}U ø= {A，B}

故 M’（[A，B]，a）= [A，B]

由于 M（{A，B}，b）= M（A，b）U M（B，b）={B}U {A，B} = {A，B}

故 M’（[A，B]，b）= [A，B]

5. 求 Z’

终态集 Z’={[A，B]，[B]}

6. 改写

重新定义：令0=[A] 1=[B] 2=[A, B]，则DFA如下所示：