【编译原理】有限自动机NFAε到NFA的探索

1 原理分析

Q&＃xff1a;有限个数状态的集合

∑&＃xff1a;输入字母表

T &＃xff1a;迁移函数

S &＃xff1a;初始状态

F &＃xff1a;结束状态

现在来介绍从 NFA-ε 到 NFA 的转换

令Q‘、∑’、T ‘、S’、F分别表示 NFA中的 有限个数状态集合、输入字母表、迁移函数、初始状态、结束状态&＃xff0c;而Q、∑、T、S、F则表示NFA-ε 中的有限个数状态集合、输入字母表、迁移函数、初始状态、结束状态&＃xff1b;那么&＃xff0c;∑‘ &＃61; ∑&＃xff0c; Q’ &＃61; Q&＃xff0c;S’ &＃61; S&＃xff0c; F‘ &＃61; {q | E(q) ∩ F≠ф } &＃xff08;其中E&＃xff08;q&＃xff09;表示q 的 ε 闭包&＃xff09;

简单来说&＃xff0c;就是看这个状态A连续空跳到达的状态B是什么&＃xff0c;如果B通过输入字母表X到达状态C&＃xff0c;则直接简化为状态A接受输入字母表B到达C&＃xff0c; 如果B没有获得

2 图解

任何输入字母表&＃xff0c;则A不进行任何操作。简单的图示如下&＃xff1a;

该图下面一连串的过程可以等价为 状态q0 吸收 x 后变成状态q2

3 实例推导

现在来看一个 NFA-ε 转为 NFA 的实例&＃xff0c;把下图转变为NFA

首先从状态X开始&＃xff0c;它能一直空跳到状态I&＃xff0c; 由于状态I 吸收 1 后变成状态 J&＃xff0c; 故状态 X 能接受 1直接变成状态 J&＃xff0c;而状态G、H、I都可省去。此外&＃xff0c;状态X也可以一直空跳到状态 A和状态 C&＃xff1b;针对状态 A&＃xff0c; 其接收 1 后变成状态 B &＃xff0c;故 X 能直接接收 1 变成状态 B&＃xff0c; 同样由于状态 C 接受 0 后变成状态 D&＃xff0c; 故 X 也能直接接收 0 后变成状态 D。到这里状态 X 全部讨论完毕。
接下来讨论状态 G&＃xff0c;由于状态 G 可由状态 X 跳转得到&＃xff0c;并且 X 已经讨论过&＃xff0c;故状态 G 可以忽略。同理&＃xff0c;状态 H、I、A、C也可以忽略。
接下来讨论状态 B&＃xff0c;状态 B 可以连续跳转到 状态 A 和状态 C&＃xff0c;由于 A 可接受 1 变成状态 B&＃xff0c; 故 B 可直接接收 1 保持自身状态不变&＃xff0c;又由于 C 可以接收 0 变成状态 D&＃xff0c;故B 也可以接收 0 变成状态 D。此外&＃xff0c;状态B也可以跳转到状态 F&＃xff0c; 由于 F 接收 1 变成状态 J&＃xff0c;故状态 B 也可以直接接收 1 变成状态 J。至此状态 B 讨论结束。
接下来讨论状态 C&＃xff0c;由于状态 C 可以连续跳转到状态 A 和状态 C&＃xff0c;由于 A 可以接收 1 变成状态 B&＃xff0c;故C 能直接接收1变成状态B&＃xff1b;由于C可接收0变成状态D&＃xff0c;故D 可直接接收0保持自身状态不变。此外&＃xff0c;状态 C也可以跳转到状态F&＃xff0c;由于状态F接收1变成状态J&＃xff0c;故状态 D也可以直接接收 1 变成状态 J。至此&＃xff0c;状态 C 讨论结束。
接下来讨论状态 F&＃xff0c;F可以由B、D经过空跳得到&＃xff0c;由于B、D已讨论过&＃xff0c;故F可以忽略。
接下来讨论状态 J&＃xff0c;由于状态 J 可以通过空跳得到状态 Y&＃xff0c;而 Y又是结束状态&＃xff0c;故 J 是一个结束状态。
接下来讨论状态Y&＃xff0c;由于状态 J 通过空跳得到状态 Y&＃xff0c;故 Y 可以忽略。
至此&＃xff0c;全部状态分析完毕&＃xff0c;其变化后的图如下