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 (a|b)(a|b|0|1), whose transition diagram is as below.

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 x, a DFA with start state s0, move(s, c) function that moves state s to a new state on input c, accepting states F.

Output: yes if D accepts x, no otherwise.

s = s0;

while (c=nextChar())!=eof do s= move(s,c);

end

if s F then

return yes;

end

return no;

/** * 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); } }

public class Simulator { public static boolean run(DFA dfa, String input) { \\You need to fill in the missing part here. \\You do not need to include the DFA class. } }

please do the missing part in the class simulator

a,b,0,1 a a.b A Its corresponding dfa.txt is: a b 01 AB A B AaB BaB BDB BOB B 1 B The format of the dfa.txt is like below: alphabet states start state final state(s) transition 1 transition_2 transition_n a,b,0,1 a a.b A Its corresponding dfa.txt is: a b 01 AB A B AaB BaB BDB BOB B 1 B The format of the dfa.txt is like below: alphabet states start state final state(s) transition 1 transition_2 transition_n