Implement a simple finite state machine (FSM) library that can be used to perform tokenization.

• States are integers represented as Java int.
• Labeled transitions are single-letter strings. They are represented as java.lang.String with length 1.
• We also support epsilon transitions. These transitions will be labeled by the empty string "".
• There can only be one initial state.
• There can be multiple final states

public class FSM { // Adds a transition from the source state to the target state. // The transition is labeled by the string label. // The label is considered as a single character symbol. If label // is the empty string, then the transition is considered // as the epsilon transition. public void add(int source, int target, String label); // Marks the initial state. public void initState(int state); // Marks a final state. This can be used multiple // times if there are multiple final states. public void finalState(int state); // Returns the states that can be reached // by the input _string_. The input is // considered as a sequence of characters. public Set reachable(String input); // Returns if the input string (sequence of chars) // is accepted by the FSM. public boolean accept(String input); // Returns the longest prefix of the input string // that is accepted by the FSM. public String matchLongest(String input); // Prints the transitions of the FSM // in the order added. public void print(); // Construct a FSM that recognizes valid Java identifiers public static FSM ID(); // Constructs a FSM that recognizes whitespaces. public static FSM Whitespace(); }

Use Java utility data structures to simplify your code. For example, to compute set union and intersection, you can use the java.util.HashSet<...>.addAll(...) and HashSet<>.retainAll(...) methods.

Check.java code that checks the implementation.

import static java.lang.System.out;

public class Check { public FSM a1; public Check() { a1 = new FSM(); a1.add(0, 1, "a"); a1.add(0, 1, "b"); a1.add(1, 1, "b"); a1.add(1, 2, "c"); a1.add(1, 0, "a"); a1.add(2, 0, ""); a1.initState(0); a1.finalState(2); a1.finalState(0); } public void Test0() { a1.print(); } public void Test1() { for(String input: new String[]{"a", "b", "c"}) { out.printf("Reachable states of \"%s\": %s ", input, a1.reachable(input)); } }

public void Test2() { for(String input: new String[]{ "a", "ab", "abc" }) { out.printf("Reachable states of \"%s\": %s ", input, a1.reachable(input)); } }

public void Test3() { for(String input: new String[]{ "a", "ab", "abc" }) { out.printf("Accept \"%s\"? %s ", input, a1.accept(input)); }

}

public void Test4() { String[] inputs = new String[] { "abbaaaa", "abccc", "aaaaaa", "abababa" }; for(String input: inputs) { out.printf("Longest \"%s\": \"%s\" ", input, a1.matchLongest(input)); } }

public void Test5() { FSM id = FSM.ID(); String[] inputs = new String[] { "hello", "1hello", "hello1", "hello world", "hello_world" }; for(String input: inputs) { out.printf("Is \"%s\" valid? %s ", input, id.accept(input)); } }

public void Test6() { FSM whitespace = FSM.Whitespace();

String[] inputs = new String[] { " hello world", "\t\t \thello world", " \t\t hello world" };

for(String input: inputs) { String ws = whitespace.matchLongest(input); String output = input.substring(ws.length()); out.printf("Whitespace removed: \"%s\" ", output); } }

public static void main(String[] args) { Check check = new Check(); check.Test0(); check.Test1(); check.Test2(); check.Test3(); check.Test4(); check.Test5(); check.Test6(); } }