自动机

自动机的幂集构造法详解

幂集构造,又叫子集构造,是一种将 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...
1 of 1

最近发布

要查看全部文章,请点击右上角“归档”