本文概述
- 将NFA转换为DFA的步骤
令，M =（Q，∑，δ，q0，F）是一个接受语言L（M）的NFA。应该存在由M’ =（Q’ ，∑’ ，q0’ ，δ’ ，F’ ）表示的等效DFA，以使L（M）= L（M’ ）。
将NFA转换为DFA的步骤步骤1：最初，Q’ = ?
步骤2：将NFA的q0加到Q’ 。然后找到从此开始状态开始的过渡。
步骤3：在Q’ 中，找到每个输入符号的可能状态集。如果这组状态不在Q’ 中，则将其添加到Q’ 中。
步骤4：在DFA中，最终状态将是包含F（NFA的最终状态）的所有状态
范例1：
将给定的NFA转换为DFA。
文章图片
解决方案：对于给定的过渡图，我们将首先构造过渡表。
| 州 | 0 | 1 |
|---|---|---|
| →q0 | 00 | 11 |
| q1 | {q1, q2} | 11 |
| *q2 | 22 | {q1, q2} |
δ'([q0], 0) = [q0]
δ'([q0], 1) = [q1]状态q1的δ’ 转换为：
δ'([q1], 0) = [q1, q2](new state generated)
δ'([q1], 1) = [q1]状态q2的δ’ 转换为：
δ'([q2], 0) = [q2]
δ'([q2], 1) = [q1, q2]现在我们将在[q1，q2]上获得δ’ 跃迁。
δ'([q1, q2], 0) = δ(q1, 0) ∪ δ(q2, 0)
= {q1, q2} ∪ {q2}
= [q1, q2]
δ'([q1, q2], 1) = δ(q1, 1) ∪ δ(q2, 1)
= {q1} ∪ {q1, q2}
= {q1, q2}
= [q1, q2]状态[q1，q2]也是最终状态，因为它包含最终状态q2。构造的DFA的过渡表将为：
| 州 | 0 | 1 |
|---|---|---|
| →[q0] | [q0] | [q1] |
| [q1] | [q1, q2] | [q1] |
| *[q2] | [q2] | [q1, q2] |
| *[q1, q2] | [q1, q2] | [q1, q2] |
文章图片
因为q2是不可达状态，所以可以消除状态q2。
范例2：
将给定的NFA转换为DFA。
文章图片
解决方案：对于给定的过渡图，我们将首先构造过渡表。
| 州 | 0 | 1 |
|---|---|---|
| →q0 | {q0, q1} | {q1} |
| *q1 | ? | {q0, q1} |
δ'([q0], 0) = {q0, q1}
= [q0, q1](new state generated)
δ'([q0], 1) = {q1} = [q1]状态q1的δ’ 转换为：
δ'([q1], 0) = ?
δ'([q1], 1) = [q0, q1]现在我们将在[q0，q1]上获得δ’ 跃迁。
δ'([q0, q1], 0) = δ(q0, 0) ∪ δ(q1, 0)
= {q0, q1} ∪ ?
= {q0, q1}
= [q0, q1]同样，
δ'([q0, q1], 1) = δ(q0, 1) ∪ δ(q1, 1)
= {q1} ∪ {q0, q1}
= {q0, q1}
= [q0, q1]就像在给定的NFA中一样，q1是最终状态，然后在DFA中无论哪里存在，q1都将成为最终状态。因此，在DFA中，最终状态为[q1]和[q0，q1]。因此，最终状态集F = {[q1]，[q0，q1]}。
构造的DFA的过渡表将为：
| 州 | 0 | 1 |
|---|---|---|
| →[q0] | [q0, q1] | [q1] |
| *[q1] | ? | [q0, q1] |
| *[q0, q1] | [q0, q1] | [q0, q1] |
文章图片
甚至我们都可以更改DFA状态的名称。
假设
A = [q0]
B = [q1]
C = [q0, q1]【从NFA到DFA的自动机转换】使用这些新名称，DFA将如下所示：
文章图片
