自动机的幂集构造法详解
幂集构造,又叫子集构造,是一种将 NFA 转换为 DFA 的算法。下面通过一个例子学习。
【例子】 这是识别 101 结尾的二进制串的 NFA。将其转换为 DFA。
分析:
NFA 的状态转移表:
0 1
-> {q0} {q0} {q0,q1}
{q1} {q2} /
{q2} / {q3}
* {q3} / / 我们逐行看,第一行产生了新的状态 {q0,q1}。考察这个状态的两个子状态 q0, q1。
当输入 0 时:
{q0} 跳至 {q0}
{q1} 跳至 {q2}
所以我们有:
同理,输入 1 时有:
据此在状态转移表添加一行 {q0,q1},得到:
0 1
-> {q0} {q0} {q0,q1}
{q1} {q2} /
{q2} / {q3}
* {q3} / /
{q0,q1} {q0,q2} {q0,q1} 重复这样的操作(称为子集构造),得到:
0 1
-> {q0} {q0} {q0,q1}
{q1} {q2} /
{q2} / {q3}
* {q3} / /
{q0,q1} {q0,q2} {q0,q1}
{q0,q2} {q0} {q0,q1,q3}
* {q0,q1,q3} {q0,q2} {q0,q1} 注:最初接受状态是 {q3},则要把所有构造出的含有 q3 的状态标记为接受。
Read more...