Algorithm 1

DFA.java

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

2 A21: DFA (3 marks) 2.1 Purpose Automaton is a machine that can run by itself. Understand how it runs by implementing it. 2.2 What you will write 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 (alb)(ab|0|1)*, whose transition diagram is as below. (B)a,b,0,1 a,b Its corresponding dfa.txt is: a b 0 1 A B Ba B 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 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). S= Input: An input string x, 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 x, no otherwise. S = So; while (c=nextChar())!=eof do | move(s,c); end if se F then | return "yes; end return "no"; Algorithm 1: Simulate DFA (dragon book p. 151) S = S = So; c= next Char(); while ( c != eof) { move(s,c); nextChar(); } if ( s is in F ) return "yes"; else return "no"; C= Figure 3.27: Simulating a DFA b b start a b b 1 2 3 a a a Figure 3.28: DFA accepting (alb)*abb public class Simulator { public static boolean run(DFA dfa, String input) { Il you need to fill in the missing part here. TIYou do not need to include the DFA class. } } Submit 21 1. To do this assignment, you need to fully understand the DFA class. Also, understand how DFA works, and how A11 works. Better to run a few DFAs manuallly on the examples in our lecture slides. Trace the process using a diagram and an actual input string. 2. The transisions correspond to the table in the slides. They are encoded inside DFA using the Map data structure. The key of the map is (state, char) represented using the string state+"_"+char. The value of the map is the next state it moves to. To put this in actual Java code, the move function can be roughly like below: current state = ...; next_state=transitions.get (current_state+"_"+next_char); 3. Simulator class should be saved in a file called Simulator.java. Save DFA.java in the same directory (say 2140), then compile them as follows: javac Simulator.java javac DFA.java 4. To run and test your code locally, you need to run the code like below: java DFA dfa.txt input.txt where dfs.txt is the actual dfa that can be downloaded from A2.pdf, and input.txt is any text file that you should create. 5. To loop over characters, you can use index of the string array to loop from 0 to the end of the string (i.e., length of the string). 2 A21: DFA (3 marks) 2.1 Purpose Automaton is a machine that can run by itself. Understand how it runs by implementing it. 2.2 What you will write 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 (alb)(ab|0|1)*, whose transition diagram is as below. (B)a,b,0,1 a,b Its corresponding dfa.txt is: a b 0 1 A B Ba B 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 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). S= Input: An input string x, 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 x, no otherwise. S = So; while (c=nextChar())!=eof do | move(s,c); end if se F then | return "yes; end return "no"; Algorithm 1: Simulate DFA (dragon book p. 151) S = S = So; c= next Char(); while ( c != eof) { move(s,c); nextChar(); } if ( s is in F ) return "yes"; else return "no"; C= Figure 3.27: Simulating a DFA b b start a b b 1 2 3 a a a Figure 3.28: DFA accepting (alb)*abb public class Simulator { public static boolean run(DFA dfa, String input) { Il you need to fill in the missing part here. TIYou do not need to include the DFA class. } } Submit 21 1. To do this assignment, you need to fully understand the DFA class. Also, understand how DFA works, and how A11 works. Better to run a few DFAs manuallly on the examples in our lecture slides. Trace the process using a diagram and an actual input string. 2. The transisions correspond to the table in the slides. They are encoded inside DFA using the Map data structure. The key of the map is (state, char) represented using the string state+"_"+char. The value of the map is the next state it moves to. To put this in actual Java code, the move function can be roughly like below: current state = ...; next_state=transitions.get (current_state+"_"+next_char); 3. Simulator class should be saved in a file called Simulator.java. Save DFA.java in the same directory (say 2140), then compile them as follows: javac Simulator.java javac DFA.java 4. To run and test your code locally, you need to run the code like below: java DFA dfa.txt input.txt where dfs.txt is the actual dfa that can be downloaded from A2.pdf, and input.txt is any text file that you should create. 5. To loop over characters, you can use index of the string array to loop from 0 to the end of the string (i.e., length of the string)