/******Given DFA.java code******/

/** * DFA format: alphabet states start state final state(s) transition_1 transition_2 ... transition_n Example DFA for RE (a|b)(a|b|0|1)* The diagram is a,b a,b,0,1 A-->B---->  finalStates; public static TreeMap transitions=new TreeMap(); /** Construct a DFA from a text file */ public DFA(String filename) throws Exception{ BufferedReader br = new BufferedReader(new FileReader(filename)); alphabet=br.readLine().trim().split(" "); String[] states=br.readLine().split(" "); startState=br.readLine().trim(); String[] finals=br.readLine().trim().split(" "); finalStates= new HashSet(Arrays.asList(finals)); String line=""; while ((line=br.readLine())!=null) { String[] transition=line.trim().split(" "); transitions.put(transition[0]+"_"+transition[1], transition[2]); } } public static void main(String[] args) throws Exception{ DFA dfa = new DFA(args[0]); String input = new BufferedReader(new FileReader(args[1])).readLine().strip(); boolean result=Simulator.run(dfa,input); BufferedWriter bw=new BufferedWriter(new FileWriter(args[2])); bw.write(result+""); bw.close(); System.out.println(input+"\t"+result); } } 

/****End DFA.java code****/

/**** Given dfa.txt file****/

 a b 0 1 A B A B A a B A b B B a B B b B B 0 B B 1 B

/*** End dfa.txt ***/

In this assignment you need to write the DFA Simulator that can run a DFA against an input string. Given a DFA and an input string, the simulator will return yes if the DFA accepts the string, return false if the string is rejected. The Simulator algorithm in pseudo code is listed in Algorithm 1. You need to rewrite it into Java code, and make it work together with the DFA.java code. You can click the high-lighted link to download DFA.java. It is also listed at the end of this document. The code you should have the same class name and method name as is listed below: public class Simulator { public static boolean run (DFA dfa, String input) { \\you need to fill in the missing part here. } } Your code should work for any DFAs and input strings. You should test your code using sample DFAs and input strings. One example is the DFA that corresponds the regular expression (ab)(alb|0|1)*, whose transition diagram is as below. (B) a,b,0.1 Its corresponding dfa.txt is: a b 0 1 B Ab B BOB B1 B The format of the dfa.txt is like below: alphabet states start state final state(s) transition 1 transition_2 transition n The first line is a set of characters, the second line is the set of states. The third line is the start state, the fourth line is the set of final states in this case it happens that there is only one final state). Input: An input string r, a DFA with start state so, move(s, c) function that moves state s to a new state on input c, accepting states F. Output: "yes" if D accepts 3, "no" otherwise. S = 90; while (crnert Char())!=cof do 1 s= move(s,c); end if se F then return "yes"; end return "no"; Algorithm 1: Simulate DFA (dragon book p. 151) In this assignment you need to write the DFA Simulator that can run a DFA against an input string. Given a DFA and an input string, the simulator will return yes if the DFA accepts the string, return false if the string is rejected. The Simulator algorithm in pseudo code is listed in Algorithm 1. You need to rewrite it into Java code, and make it work together with the DFA.java code. You can click the high-lighted link to download DFA.java. It is also listed at the end of this document. The code you should have the same class name and method name as is listed below: public class Simulator { public static boolean run (DFA dfa, String input) { \\you need to fill in the missing part here. } } Your code should work for any DFAs and input strings. You should test your code using sample DFAs and input strings. One example is the DFA that corresponds the regular expression (ab)(alb|0|1)*, whose transition diagram is as below. (B) a,b,0.1 Its corresponding dfa.txt is: a b 0 1 B Ab B BOB B1 B The format of the dfa.txt is like below: alphabet states start state final state(s) transition 1 transition_2 transition n The first line is a set of characters, the second line is the set of states. The third line is the start state, the fourth line is the set of final states in this case it happens that there is only one final state). Input: An input string r, a DFA with start state so, move(s, c) function that moves state s to a new state on input c, accepting states F. Output: "yes" if D accepts 3, "no" otherwise. S = 90; while (crnert Char())!=cof do 1 s= move(s,c); end if se F then return "yes"; end return "no"; Algorithm 1: Simulate DFA (dragon book p. 151)