COP 3530 Section U03 Spring 2017 Homework #2 =========== Due: Febuary 20th, 2017 A deterministic finite state acceptor, DFSA, consists of a set of states, a set of inputs, an initial state, a set of final states, and a next state function. The next state function assigns to each pair a state, called the next state. For example, let's look at the DFSA that has states 0, 1, 2, 3, 4, the inputs 'a' and 'b', the initial state 0, the final state 4, and the next state function below: next state (0,'a') = 0 next state (0,'b') = 1 next state (1,'a') = 2 next state (1,'b') = 1 next state (2,'a') = 0 next state (2,'b') = 3 next state (3,'a') = 4 next state (3,'b') = 1 next state (4,'a') = 0 next state (4,'a') = 3 The next state function can be generalized to a function (next state)* that assigns a state to every pair of , as follows: (next state)* (state, "") = state // rule 1 (next state)* (state, 'a') = next state(state, "a") if 'a' is a symbol in the alphabet // rule 2 (next state)* (state, w + 'a') = next state( (next state)* (state,w), 'a') if 'a' is a symbol in the alphabet // rule 3 For the above DFSA, (next state)* (1, "aba") = next State ( (next state)*(1,"ab"), 'a') // rule 3 = next state ( next state ( (next state)*(1,"a"), 'b' , 'a') // rule 3 = next state ( next state ( next state ((next state)* (1,""),'a'), 'b') , 'a') // rule 3 = next state ( next state ( next state ( 1,'a'), 'b') , 'a') // rule 1 = next state ( next state ( 2, 'b') , 'a') // rule 2 = next state ( 3, 'a') // rule 2 = 4 // rule 2 A string w is accepted by a DFSA if it carries the initial state into a final state, i.e. (next state)*(initial stste, w) is a final state. Here we deal with DFSA's that recognize a pattern, i.e. given an input string, the DFSA must reach a final state every time the pattern occurs in the input string. For example, let the pattern be "baba" and the input string be "abababaa". We start the DFSA in the initial state, and we must reach a final state twice, one for the string "baba" that starts at index 1 and the second time for the "baba" that starts at index 3. For this problem, the states are the prefixes of the pattern in our case, "", "b", "ba", "bab", "baba". The initial state is "" and the final state is "baba". It remains to show how to find the next state function. This is easy. If the state is the string u and the input is the character c, we append c at the end of u and get v = u + c. The next state is the longest suffix of v that is a prefix of the pattern. For example, if the current state is u="ba" and the input is c = 'a' we get v = "baa" the suffixes of v, in the decreasing order of length are "baa", "aa", "a", and "". "baa", "aa", and "a" are not prefixes of "baba", but "" is. So, next state("ba","a") = "" On the other side if the state is u = "ba" and c = 'b', v = u + c = "bab". The prefixes of v are "bab", "ab", "b" and "". "bab" is a prefix of "baba", and next state("ba","b") = "bab" ___________________________________________________________________________________________________________________________________________ Recall that a prefix of a string w is a substring u that begins w, i.e. w = uv for some v, and a suffix of a string w is a substring v that end w, i.e. w = uv for some u. ___________________________________________________________________________________________________________________________________________ Now let's get to the program. You are given the class Pair, shown below. // a pair of two items // it has the fields first and second, a constructor, the get and set metods // and overrides toString() public class Pair { // the fields private U first; private V second; // the constructor // form an object with objects f and s public Pair(U f, V s) { first = f; second = s; } // the accessor methods public U getFirst() { return first; } public V getSecond() { return second; } // the set methods public void setFirst(U newFirst) { first = newFirst; } public void setSecond(V newSecond) { second = newSecond; } // the to string method public String toString() { return getClass().getSimpleName() + "[first = " + first + "]{second = " + second + "]"; } } First you must write the class PairComparator shown beneath. import java.util.*; // orders the pairs first by the integer, and if the integers are the same // by the character public class PairComparator implements Comparator> { public int compare(Pair o1, Pair o2) { // you write it } } We represent a DFSA as an Fsa object, where the states are represented by whole numbers, 0,1, .. . This numbers represent the lengths of the prefixes of the patterns. So, for the pattern "baba", the states are 0, 1, 2, 3, 4, that are the lengths of the prefixes "", "b", "ba", "bab", "baba". The initial state is 0, and the final state is the length of the pattern. You must complete the class Fsa. The comments above a method tell you you need to do. Feel free to use helper methods, but make them private. import java.util.*; // construct a deterministic FSA that accepts a given pattern public class Fsa { // the fields private char[] alphabet; // the input alpahbet private String word; private TreeMap,Integer> nextState; private int accept; // the final state // construct the FSA for the word w and for the alphabet sigma // first check if either sigma or w or both are null. If this is true // throw a null pointer exception // Then check that every symbol of w occurs in sigma. If not, // throw an illegal argument exception // Then create the nextState map by using the method (suffix, prefix) described above public Fsa(char[] sigma, String w) { // you write it } // the get methods // return next state public TreeMap,Integer> getNextState() { return nextState; } // return the accept public int getAccept() { return accept; } } Try your program with the driver below. import java.util.*; public class Spring17DataStructuresHw2 { public static void main(String[] args) { char[] alphabet = { 'a', 'b'}; String word = "baba"; Fsa acceptor = new Fsa(alphabet, word); TreeMap,Integer> map = acceptor.getNextState(); printMap("The next state map", map); int finalState = acceptor.getAccept(); processInput(map, "abababaa",finalState); } // print a map public static void printMap(String msg, Map m) { System.out.println(msg + ":"); Set> entries = m.entrySet(); for ( Map.Entry thisPair :entries) { System.out.print(thisPair.getKey() + "; "); System.out.println(thisPair.getValue()); } } // traverse in public static void processInput(TreeMap, Integer> m, String text, int finalState) { int currentState = 0; for (int i = 0; i < text.length(); i++) { // get the input char in = text.charAt(i); Pair key = new Pair<>(currentState,in); int nextState = m.get(key); if (nextState == finalState) System.out.println("Match at " + (i - finalState + 1) ); currentState = nextState; } } } The output should be: run: The next state map: Pair[first = 0]{second = a]; 0 Pair[first = 0]{second = b]; 1 Pair[first = 1]{second = a]; 2 Pair[first = 1]{second = b]; 1 Pair[first = 2]{second = a]; 0 Pair[first = 2]{second = b]; 3 Pair[first = 3]{second = a]; 4 Pair[first = 3]{second = b]; 1 Pair[first = 4]{second = a]; 0 Pair[first = 4]{second = b]; 3 Match at 1 Match at 3