lihongjie0209
commented
3 years ago
public class NFA2DFA {
@Data
@AllArgsConstructor
public static class Trans {
String from;
String to;
String input;
String remark;
}
@Data
public static class XFA {
private String start;
private Set<String> finish;
private List<Trans> transList;
private String remark;
public Set<String> alphabet() {
return transList.stream().map(item -> item.getInput()).filter(item -> !item.equals("")).collect(Collectors.toSet());
}
public Set<String> eClouse(String status) {
HashSet<String> ans = new HashSet<>();
Set<String> todos = findEClosure(status);
LinkedList<String> todoList = new LinkedList<>(todos);
while (!todoList.isEmpty()) {
String s = todoList.pollFirst();
boolean add = ans.add(s);
if (add) {
Set<String> eClosure = findEClosure(s);
todoList.addAll(eClosure);
}
}
ans.add(status);
return ans;
}
private Set<String> findEClosure(String status) {
return transList.stream()
.filter(item -> item.getFrom().equals(status) && item.getInput().equals(""))
.map(item -> item.getTo()).collect(Collectors.toSet());
}
public Set<String> run(Set<String> status, String input) {
HashSet<String> ans = new HashSet<>();
for (String s : status) {
Set<String> next = this.transList.stream()
.filter(item -> item.getFrom().equals(s) && item.getInput().equals(input))
.map(item -> item.getTo()).collect(Collectors.toSet());
for (String n : next) {
Set<String> set = this.eClouse(n);
ans.addAll(set);
}
ans.addAll(next);
}
return ans;
}
}
@Data
@AllArgsConstructor
static class Job{
String id;
Set<String> status;
}
public XFA nfa2dfa(XFA nfa) {
int id = 0;
XFA ans = new XFA();
String start = nfa.start;
Set<String> newStatus = nfa.eClouse(start);
ans.start = id + "";
ans.transList = new ArrayList<>();
ans.remark = newStatus.stream().collect(Collectors.joining(","));
Set<String> alphabet = nfa.alphabet();
LinkedList<Job> todoList = new LinkedList<>();
todoList.add(new Job(ans.start, newStatus));
while (!todoList.isEmpty()) {
Job job = todoList.pollFirst();
for (String s : alphabet) {
Set<String> next = nfa.run(job.status, s);
if (!next.isEmpty()) {
ans.transList.add(new Trans(id + "", ++id + "", s, next.stream().collect(Collectors.joining(","))));
todoList.add(new Job(id + "", next));
}
}
}
return ans;
}
public static void main(String[] args) {
XFA xfa = new XFA();
xfa.start = "1";
xfa.finish = new HashSet<>(Arrays.asList("8"));
xfa.transList = new ArrayList<>();
xfa.transList.add(new Trans("1", "2", "", ""));
xfa.transList.add(new Trans("1", "6", "", ""));
xfa.transList.add(new Trans("2", "3", "a", ""));
xfa.transList.add(new Trans("3", "4", "", ""));
xfa.transList.add(new Trans("4", "5", "b", ""));
xfa.transList.add(new Trans("5", "8", "", ""));
xfa.transList.add(new Trans("6", "7", "a", ""));
xfa.transList.add(new Trans("7", "8", "", ""));
System.out.println(xfa.toString());
XFA dfa = new NFA2DFA().nfa2dfa(xfa);
System.out.println(dfa.toString());
}
}
考虑下列有字母表{0, 1}的NFA:
我们将构造一个等价的DFA；最终结果展示在后面。我们开始于开始状态。NFA开始于状态1，但是它可以不查看任何输入就沿着ε边前进到状态2和3。所以我们必须认为它最初同时处于这些状态。我们为DFA建立一个初始状态并标记上“{1,2,3}”。
接着，假设我们看到输入字符0。如果我们处在状态1，我们可以沿着标记0的边前进到状态2。如果我们处在状态3，我们可以前进到状态4。如果我们处在状态2，我们就被粘住了；没有0边出于状态2。这意味着NFA放弃从状态1沿着ε边到状态2的这条旧路径；它现在处在状态2和4之中。我们在DFA中增加从开始状态到标记着“{2,4}”的一个新状态的标记着“0”的一个新边。
假设我们最初看到的输入字符是1。则状态1的两个路径和状态3的路径不能前进，但状态2的路径可以并且它分支了：它同时保持在状态2和前进到状态4。因此，NFA现在在状态2和4中，就是说完全同于对0输入字符，但原因不同。我们在DFA中向从开始状态到现存的“{2,4}”状态的边增加标记“1”。
现在，假设我们在{2,4}状态并看见了字符1。在状态4中的路径不能前进，但是在状态2再次去到了2或4二者。我们仍在状态{2,4}中。如果我们看到了字符0，我们可以从从状态4前进到状态3，但不能从状态2前进到状态3。此外，在到达状态3之后，我们分支并也从ε-边到达状态2。结果是处在状态2和3。我们在DFA增加标记“{2,3}”的一个状态和从{2,4}到{2,3}的标记“0”的一个边。
如果我们在状态{2,3}看到了字符1，状态3的路径不能前进，但是在状态2的路径前进到状态2和4，同前面一样这回到了节点{2,4}。如果我们看到字符0，状态2的路径不能继续，而在状态3的路径可以到达状态4。因此，我们只能到达状态4。我们在DFA中建立标记“{4}”的一个新状态和从{2,3}到{4}的标记“0”的一个边。
最后，如果我们在状态{4}并看到输入0，我们同前面一样前进到状态2和3，所以，在DFA中建立从{4}到{2,3}的一个标记“0”的边。如果我们看到了输入1，我们余下的所有路径都被粘住了而机器必须拒绝输入字符串。怎么办呢?我们在DFA中建立标记“
现在我们已经考虑了所有可能情况。我们必须决定的是在这个DFA哪个状态应当接受。因为NFA接受输入字符串，如果任何它的路径结束于接受状态，我们可以通过设置所有包含接受NFA状态的DFA状态节点，为接受状态了模仿，也就是设置{1,2,3}, {2,3}, {2,4}和{4}为接受状态。结果的DFA完全接受同最初的NFA同样的字符串集合。注意这个DFA比最初的NFA更大。