-
Notifications
You must be signed in to change notification settings - Fork 0
/
NFA.java
86 lines (74 loc) · 3.86 KB
/
NFA.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
import java.io.Serializable;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
class NFA implements Serializable {
// Клас, представляващ недетерминиран краен автомат.
private Map<Integer, Set<Transition>> transitions; // Мап, който съхранява преходите на автомата.
private int initialState; // Началното състояние на автомата.
private Set<Integer> finalStates; // Множеството от финални състояния на автомата.
public boolean firstTransition = true;
// Конструктор за инициализиране на преходите, началното и финалните състояния.
public NFA() {
transitions = new HashMap<>();
finalStates = new HashSet<>();
}
// Метод за добавяне на преход към автомата.
public void addTransition(int currentState, char symbol, int nextState) {
Transition transition = new Transition(symbol, nextState);
Set<Transition> currentTransitions = transitions.computeIfAbsent(currentState, k -> new HashSet<>());
boolean isDuplicate = currentTransitions.stream()
.anyMatch(t -> t.getSymbol() == symbol && t.getNextState() == nextState);
if (isDuplicate) {
System.out.println("Transition already exists: " + currentState + " -> " + nextState + " (" + symbol + ")");
} else {
currentTransitions.add(transition);
firstTransition = false;
System.out.println("Transition added to NFA");
}
}
// Метод за задаване на началното състояние.
public void setInitialState(int state) {
initialState = state;
}
// Метод за връщане на началното състояние.
public int getInitialState() {
return initialState;
}
// Метод за добавяне на финално състояние.
public void addFinalState(int state) {
finalStates.add(state);
}
// Метод за проверка дали езикът на автомата е празен.
public boolean isEmptyLanguage() {
Set<Integer> reachableStates = new HashSet<>();
exploreStates(initialState, reachableStates);
return Collections.disjoint(reachableStates, finalStates);
}
// Рекурсивен метод за разглеждане на достижимите състояния от дадено състояние.
private void exploreStates(int currentState, Set<Integer> reachableStates) {
reachableStates.add(currentState);
Set<Transition> currentTransitions = transitions.get(currentState);
if (currentTransitions != null) {
for (Transition transition : currentTransitions) {
if (!reachableStates.contains(transition.getNextState())) {
exploreStates(transition.getNextState(), reachableStates);
}
}
}
}
// Метод за извеждане на преходите в автомата.
public void printTransitions() {
for (Map.Entry<Integer, Set<Transition>> entry : transitions.entrySet()) {
int currentState = entry.getKey();
Set<Transition> currentTransitions = entry.getValue();
for (Transition transition : currentTransitions) {
int nextState = transition.getNextState();
char symbol = transition.getSymbol();
System.out.println("Transition: " + currentState + " -> " + nextState + " (" + symbol + ")");
}
}
}
}