Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Here is the 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
Here is the 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 TreeMaptransitions=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); } }
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)(a|6|0|1)*, whose transition diagram is as below. (B)a,b,0,1 a,b Its corresponding dfa.txt is: a b 0 1 AB A B Ba B Bb B B 0 B 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). 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=next Char())!=eof do s= move(s,c); end if s E F then return "yes"; end return no; 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)(a|6|0|1)*, whose transition diagram is as below. (B)a,b,0,1 a,b Its corresponding dfa.txt is: a b 0 1 AB A B Ba B Bb B B 0 B 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). 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=next Char())!=eof do s= move(s,c); end if s E F then return "yes"; end return no
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started