FSA_Validator

1
import java.util.ArrayList;
2
import java.util.HashMap;
3
import java.util.HashSet;
4

5
/**
6
 * Class that represents Finite State Machine.
7
 */
8
public class FSA {
9
    /**
10
     * Array of states.
11
     */
12
    ArrayList<String> states = new ArrayList<>();
13
    /**
14
     * Array with alphabet.
15
     */
16
    ArrayList<String> alphabet = new ArrayList<>();
17
    /**
18
     * Array with Initial states.
19
     */
20
    ArrayList<String> initialStates = new ArrayList<>();
21
    /**
22
     * Array with Final states.
23
     */
24
    ArrayList<String> finalStates = new ArrayList<>();
25
    /**
26
     * Array with Transitions.
27
     */
28
    ArrayList<String[]> transitions = new ArrayList<>();
29
    /**
30
     * The Warnings.
31
     */
32
    HashSet<String> warnings = new HashSet<>();
33
    /**
34
     * The Undirected graph.
35
     * <p>
36
     * key : state, value : child states
37
     */
38
    HashMap<String, HashSet<String>> undirectedGraph = new HashMap<>();
39
    /**
40
     * The Directed graph.
41
     * <p>
42
     * key : state, value : {key : transition, value : child states}
43
     */
44
    HashMap<String, HashMap<String, HashSet>> directedGraph = new HashMap<>();
45
    /**
46
     * Contains {@code true} if this {@link FSA} is deterministic, otherwise {@code false}.
47
     */
48
    boolean deterministic = true;
49
    /**
50
     * Contains {@code true} if this {@link FSA} is complete, otherwise {@code false}.
51
     */
52
    boolean complete = true;
53

54
    /**
55
     * Instantiates a new FSA.
56
     *
57
     * @param data input strings
58
     * @throws FSAException the FSA Exception
59
     */
60
    FSA(ArrayList<String> data) throws FSAException {
61
        processData(data);
62

63
        allStatesReachable();
64
        isDisjoint();
65
        isDeterministic();
66
        isComplete();
67
    }
68

69
    /**
70
     * Handles all input strings.
71
     *
72
     * @param data input strings
73
     * @throws FSAException the FSA Exception
74
     */
75
    private void processData(ArrayList<String> data) throws FSAException {
76
        processStates(data.get(0));
77
        processAlphas(data.get(1));
78
        processInitState(data.get(2));
79
        processFinalState(data.get(3));
80
        processTransitions(data.get(4));
81

82
        for (String state : this.states) {
83
            this.undirectedGraph.put(state, new HashSet<>());
84
            this.directedGraph.put(state, new HashMap<>());
85
            for (String a : this.alphabet) {
86
                this.directedGraph.get(state).put(a, new HashSet<>());
87
            }
88
        }
89

90
        for (String[] transition : this.transitions) {
91
            this.undirectedGraph.get(transition[0]).add(transition[2]);
92
            this.undirectedGraph.get(transition[2]).add(transition[0]);
93

94
            this.directedGraph.get(transition[0]).get(transition[1]).add(transition[2]);
95
        }
96

97

98
    }
99

100
    /**
101
     * Handles input string with {@code states}.
102
     *
103
     * @param s input strings
104
     * @throws FSAException the FSA Exception
105
     */
106
    private void processStates(String s) throws FSAException {
107
        if (!s.startsWith("states=[") || !s.endsWith("]")) {
108
            throw new FSAException(Messages.E5.getValue());
109
        }
110

111
        String[] states = s.substring(8, s.length() - 1).split(",");
112
        for (String state : states) {
113
            if (state.length() == 0) {
114
                continue;
115
            }
116

117
            if (!FSA.isGoodStateName(state)) {
118
                throw new FSAException(Messages.E5.getValue());
119
            }
120
            this.states.add(state);
121
        }
122
    }
123

124
    /**
125
     * Handles input string with {@code alphabet}.
126
     *
127
     * @param s input strings
128
     * @throws FSAException the FSA Exception
129
     */
130
    private void processAlphas(String s) throws FSAException {
131
        if (!s.startsWith("alpha=[") || !s.endsWith("]")) {
132
            throw new FSAException(Messages.E5.getValue());
133
        }
134

135
        String[] alphas = s.substring(7, s.length() - 1).split(",");
136
        for (String alpha : alphas) {
137
            if (alpha.length() == 0) {
138
                continue;
139
            }
140

141
            if (!FSA.isGoodAlphaName(alpha)) {
142
                throw new FSAException(Messages.E5.getValue());
143
            }
144
            this.alphabet.add(alpha);
145
        }
146
    }
147

148
    /**
149
     * Handles input string with {@code initialStates}.
150
     *
151
     * @param s input strings
152
     * @throws FSAException the FSA Exception
153
     */
154
    private void processInitState(String s) throws FSAException {
155
        if (!s.startsWith("init.st=[") || !s.endsWith("]")) {
156
            throw new FSAException(Messages.E5.getValue());
157
        }
158

159
        String[] initStates = s.substring(9, s.length() - 1).split(",");
160

161
        for (String state : initStates) {
162
            if (state.length() == 0) {
163
                continue;
164
            }
165
            if (!this.states.contains(state)) {
166
                throw new FSAException(Messages.E1.getValue().formatted(state));
167
            }
168
            this.initialStates.add(state);
169
        }
170

171
        if (this.initialStates.size() < 1) {
172
            throw new FSAException(Messages.E4.getValue());
173
        }
174
        if (this.initialStates.size() > 1) {
175
            throw new FSAException(Messages.E5.getValue());
176
        }
177
    }
178

179
    /**
180
     * Handles input string with {@code finalStates}.
181
     *
182
     * @param s input strings
183
     * @throws FSAException the FSA Exception
184
     */
185
    private void processFinalState(String s) throws FSAException {
186
        if (!s.startsWith("fin.st=[") || !s.endsWith("]")) {
187
            throw new FSAException(Messages.E5.getValue());
188
        }
189

190
        String[] finalStates = s.substring(8, s.length() - 1).split(",");
191
        for (String state : finalStates) {
192
            if (state.length() == 0) {
193
                continue;
194
            }
195
            if (!this.states.contains(state)) {
196
                throw new FSAException(Messages.E1.getValue().formatted(state));
197
            }
198
            this.finalStates.add(state);
199
        }
200

201
        if (this.finalStates.size() < 1) {
202
            this.warnings.add(Messages.W1.getValue());
203
        }
204
    }
205

206
    /**
207
     * Handles input string with {@code transitions}.
208
     *
209
     * @param s input strings
210
     * @throws FSAException the FSA Exception
211
     */
212
    private void processTransitions(String s) throws FSAException {
213
        if (!s.startsWith("trans=[") || !s.endsWith("]")) {
214
            throw new FSAException(Messages.E5.getValue());
215
        }
216

217
        String[] transitions = s.substring(7, s.length() - 1).split(",");
218
        for (String trans : transitions) {
219
            if (trans.length() == 0) {
220
                continue;
221
            }
222
            String[] transition = trans.split(">");
223

224
            if (!this.states.contains(transition[0])) {
225
                throw new FSAException(Messages.E1.getValue().formatted(transition[0]));
226
            }
227
            if (!this.alphabet.contains(transition[1])) {
228
                throw new FSAException(Messages.E3.getValue().formatted(transition[1]));
229
            }
230
            if (!this.states.contains(transition[2])) {
231
                throw new FSAException(Messages.E1.getValue().formatted(transition[2]));
232
            }
233

234
            if (transition.length != 3) {
235
                throw new FSAException(Messages.E5.getValue());
236
            }
237
            this.transitions.add(transition);
238
        }
239
    }
240

241
    /**
242
     * Checks if name for {@code State} is good.
243
     *
244
     * @param s name
245
     * @return {@code true} if name is good, otherwise {@code false}
246
     */
247
    public static boolean isGoodStateName(String s) {
248
        String alphabet = "abcdefghijklmnopqrstuvwxyz0123456789";
249

250
        for (char c : s.toCharArray()) {
251
            if (alphabet.indexOf(c) < 0) {
252
                return false;
253
            }
254
        }
255

256
        return true;
257
    }
258

259
    /**
260
     * Checks if name for {@code alphabet} is good.
261
     *
262
     * @param s name
263
     * @return {@code true} if name is good, otherwise {@code false}
264
     */
265
    public static boolean isGoodAlphaName(String s) {
266
        String alphabet = "abcdefghijklmnopqrstuvwxyz0123456789_";
267

268
        for (char c : s.toCharArray()) {
269
            if (alphabet.indexOf(c) < 0) {
270
                return false;
271
            }
272
        }
273

274
        return true;
275
    }
276

277
    /**
278
     * Checks if all states of this {@link FSA} are reachable from initial state.
279
     */
280
    private void allStatesReachable() {
281
        ArrayList<String> visited = recursiveSearchInDirectedGraph(this.initialStates.get(0), new ArrayList<>());
282
        if (visited.size() < this.states.size()) {
283
            warnings.add(Messages.W2.getValue());
284
        }
285
    }
286

287
    /**
288
     * Checks if this {@link FSA} has some disjoint states.
289
     */
290
    private void isDisjoint() throws FSAException {
291
        ArrayList<String> visited = recursiveSearchInUndirectedGraph(this.initialStates.get(0), new ArrayList<>());
292
        if (visited.size() < this.states.size()) {
293
            throw new FSAException(Messages.E2.getValue());
294
        }
295
    }
296

297
    /**
298
     * Checks if this {@link FSA} is deterministic.
299
     *
300
     * @return {@code true} if this {@link FSA} is deterministic, otherwise {@code false}
301
     */
302
    private boolean isDeterministic() {
303
        for (HashMap<String, HashSet> transition : this.directedGraph.values()) {
304
            for (HashSet<String> states : transition.values()) {
305
                if (states.size() > 1) {
306
                    this.deterministic = false;
307
                    this.warnings.add(Messages.W3.getValue());
308
                }
309
            }
310
        }
311
        return this.deterministic;
312
    }
313

314
    /**
315
     * Checks if this {@link FSA} is complete.
316
     *
317
     * @return {@code true} if this {@link FSA} is complete, otherwise {@code false}
318
     */
319
    private boolean isComplete() {
320
        if (!isDeterministic()) {
321
            this.complete = false;
322
        }
323
        for (HashMap<String, HashSet> transition : this.directedGraph.values()) {
324
            for (HashSet<String> states : transition.values()) {
325
                if (states.size() == 0) {
326
                    this.complete = false;
327
                }
328
            }
329
        }
330
        return this.complete;
331
    }
332

333

334
    /**
335
     * Checks which states are joint.
336
     *
337
     * @return array with visited states
338
     */
339
    private ArrayList<String> recursiveSearchInUndirectedGraph(String start, ArrayList<String> visited) {
340
        for (String state : this.undirectedGraph.get(start)) {
341
            if (!visited.contains(state)) {
342
                visited.add(state);
343
                recursiveSearchInUndirectedGraph(state, visited);
344
            }
345
        }
346
        return visited;
347
    }
348

349
    /**
350
     * Checks which states are reachable from initial state.
351
     *
352
     * @return array with visited states
353
     */
354
    private ArrayList<String> recursiveSearchInDirectedGraph(String start, ArrayList<String> visited) {
355
        for (HashSet<String> states : this.directedGraph.get(start).values()) {
356
            for (String state : states) {
357
                if (!visited.contains(state)) {
358
                    visited.add(state);
359
                    recursiveSearchInDirectedGraph(state, visited);
360
                }
361
            }
362
        }
363
        return visited;
364

365
    }
366
}
367