-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNonempty.java
93 lines (57 loc) · 2.33 KB
/
Nonempty.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.*;
public class Nonempty {
public static boolean pathFound = false;
public static boolean print = true;
public static void dfs(DFA d1) {
//Get relevant data and pass it to dfs function
String start = d1.getStartState();
ArrayList<String> tmpDests = d1.getFinalStates();
ArrayList<String> destinations = new ArrayList<String>();
for(String s : tmpDests)destinations.add(s.replaceAll("\\s",""));
Map<String, Map<String, String>> adjacent = d1.getTransitions();
ArrayList<String> states = d1.getStates();
ArrayList<String> visited = new ArrayList<String>();
Stack<String> string = new Stack<String>();
List<String> alphabet = Arrays.asList(d1.getAlphabet());
search(start,destinations,adjacent,states, visited, string, alphabet);
if(!pathFound) {
if(print)System.out.println("language empty");
}
}
public static boolean dfsNoPrint(DFA d1) {
print = false;
dfs(d1);
if(pathFound) {
return true;
}else {
return false;
}
}
public static void search(String current, ArrayList<String> destinations, Map<String, Map<String, String>> adjacent, ArrayList<String> states, ArrayList<String> visited, Stack<String> string, List<String> alphabet) {
if(pathFound)return;
//Normal DFS
//Add current item to visited list, if it is a final state return, else check adjacent paths and recurse.
if(destinations.contains(current)) { //If we are currently at an accept state then the language is non empty
if(print)System.out.print("language non-empty - ");
if(string.size() == 0) {
if(print)System.out.println("e accepted");
}else {
if(print)for(String s : string) System.out.print(s);
if(print)System.out.println(" accepted");
}
pathFound=true;
return;
}
visited.add(current.replaceAll("\\s",""));
for(String alpha : alphabet) {
if(!visited.contains(adjacent.get(current.replaceAll("\\s","")).get(alpha))) {
String destination = adjacent.get(current.replaceAll("\\s","")).get(alpha);
//push the new symbol to the stack, we use the index instead of hardcoding in case the input alphabet is b,a instead of a,b
//recursion to continue searching
string.push(alpha);
search(destination,destinations,adjacent,states, visited, string, alphabet);
}
}
string.clear();
}
}