Overview The purpose of this assignment is to further your understanding of the equivalence between nondeterministic and deterministic finite automata. Recall that a deterministic finite automaton (DFA) is defined as a 5-tuple of the form (Q, E, F, 90,8) where: Q is a finite set of states; . is an input alphabet; .FC is a set of final states; 90 Q is the initial (or start) state; and 8:QxQ is a transition function while a nondeterministic finite automaton (NFA) is a 5-tuple of the form (Q, E, F, 90,8) where: Q is a finite set of states; . is an input alphabet; . FC is a set of final states; .90 Q is the initial (or start) state; and .8: Qx (U{E}) + P(Q) is a transition function Also recall both from the reading and lecture, that these two structures are equivalent to each other. In otherwords, for every DFA there is an equivalent NFA and vice versa. An important aspect of the proof of this theorem is its structure - being a constructive proof, it in essence outlines an algorithm which given an NFA as its input, will generate the equivalent DFA. Your goal for this assignment is to realize this construction as an actual program. Specification Define a program called NFAConvert which will accept as its input the name of a file containing a textual representation of a nondeterministic finite automaton, and will output in the same format a textual representation of the equivalent deterministic finite automaton. NFA Input File Specification Because every DFA is by definition also an NFA, the input format will be the same as for your prior project. Consider the NFA, Mo shown in the figure below: Mo will be represented in plain text form as follows: 1 % O 2. 3 A B C 4 5 D 'Line numbers are included for reference only. 0 0 0 0 start - {0,1) 1 0 0 D 6 E 7 F 8 G 9 10 11 H I J % Sigma 12 0 13 14 15 1 % F . 16 17 18 B C 19 20 21 D E H 22 I 23 % QO 24 A 25 % Delta 26 27 A1 C 28 BOB 29 B 1 E 30 COD 31 C1 C 32 DOB 33 D1 G 34 E OF 35 E 1 C 36 FOB 37 F 1 I 38 GOH 39 G1 C 40 HOB 41 42 43 H1 ] I OJ I 1 C JOJ J 1 ) 44 43 Note that in this representation, those lines preceded by a % sign (i.e., lines 1, 12, 15, 25, and 27) are to be treated as single line comments in Java - any content on the line after the % sign is to be ignored and is entirely optional. Also note, that for this assignment you are guaranteed the following about the NFA input file: the NFA within it is correctly specified (i.e., is both a a NFA, and in the correct textual form); that the order of the NFA's constituent parts are as in the example above (which by design corresponds with how the definition of a DFA is formulated); and empty string transitions will designated by a single underscore '_' (e.g., the triple ) _ A would represent an empty string transition from state ) to state A). Usage The program NFAConvert is intended to be run via the following command-line invocation: $ java NFAConver input.txt If no input file is specified or if the input file is not found, an appropriate error message must be displayed. For example: 1 $ java NFAConvert NFAConvert: no input file specified 2 3 4 $ java NFAConvert no-such-file.txt NFAConvert: the file 'no-such-file.txt' could not be opened 5 If a valid file is specified as input, then the output of the program will be the equivalent DFA in plain text form (using the same format as that input DFA). The DFA is to be obtained using the same algorithm discussed both in lecture and in the reading. As an example, using the file input.txt mentioned above, your program should behave as follows23. 2 3 4 5 6 7 $ java NFAConvert input.txt % 0 {A} {B} {C} {D} {E} {F} {G} {H} 8 9 10 2 Note that in the example output there is exactly one space between the string and its results. As before, line numbers are included for reference only. 3Recall that states of the resulting DFA are sets of states of the input NFA. As a consequence, the order of their elements is irrelevant. The same is true of those constituent parts of the DFA that are themselves sets. Furthermore, for simplicity, you may use square brackets instead of braces when converting sets to string form. 11 12 {I} {J} % Sigma 13 14 O 15 1 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 % F {A} {B} {C} {D} {E} {H} {I} % QO {A} % Delta {A} {B} {A} 1 {C} {B} {B} {B} 1 {E} {C} o {D} {C} 1 {C} {D} {B} {D} 1 {G} {E} o {F} {E} 1 {C} {F} o {B} {F} 1 {I} {G} o {H} {G} 1 {C} {H} {B} {H} 1 {J} {I} o {3} {I} 1 {C} {J} o {J} {J} 1 {3} 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 Compilation Notes Your program must compile using the following command-line invocation: 1 $ javac *.java Do not submit any IDE specific files and in the interest of simplicity do not use packages for this assignment. If your program does not compile using the command mentioned above you will receive no credit. Overview The purpose of this assignment is to further your understanding of the equivalence between nondeterministic and deterministic finite automata. Recall that a deterministic finite automaton (DFA) is defined as a 5-tuple of the form (Q, E, F, 90,8) where: Q is a finite set of states; . is an input alphabet; .FC is a set of final states; 90 Q is the initial (or start) state; and 8:QxQ is a transition function while a nondeterministic finite automaton (NFA) is a 5-tuple of the form (Q, E, F, 90,8) where: Q is a finite set of states; . is an input alphabet; . FC is a set of final states; .90 Q is the initial (or start) state; and .8: Qx (U{E}) + P(Q) is a transition function Also recall both from the reading and lecture, that these two structures are equivalent to each other. In otherwords, for every DFA there is an equivalent NFA and vice versa. An important aspect of the proof of this theorem is its structure - being a constructive proof, it in essence outlines an algorithm which given an NFA as its input, will generate the equivalent DFA. Your goal for this assignment is to realize this construction as an actual program. Specification Define a program called NFAConvert which will accept as its input the name of a file containing a textual representation of a nondeterministic finite automaton, and will output in the same format a textual representation of the equivalent deterministic finite automaton. NFA Input File Specification Because every DFA is by definition also an NFA, the input format will be the same as for your prior project. Consider the NFA, Mo shown in the figure below: Mo will be represented in plain text form as follows: 1 % O 2. 3 A B C 4 5 D 'Line numbers are included for reference only. 0 0 0 0 start - {0,1) 1 0 0 D 6 E 7 F 8 G 9 10 11 H I J % Sigma 12 0 13 14 15 1 % F . 16 17 18 B C 19 20 21 D E H 22 I 23 % QO 24 A 25 % Delta 26 27 A1 C 28 BOB 29 B 1 E 30 COD 31 C1 C 32 DOB 33 D1 G 34 E OF 35 E 1 C 36 FOB 37 F 1 I 38 GOH 39 G1 C 40 HOB 41 42 43 H1 ] I OJ I 1 C JOJ J 1 ) 44 43 Note that in this representation, those lines preceded by a % sign (i.e., lines 1, 12, 15, 25, and 27) are to be treated as single line comments in Java - any content on the line after the % sign is to be ignored and is entirely optional. Also note, that for this assignment you are guaranteed the following about the NFA input file: the NFA within it is correctly specified (i.e., is both a a NFA, and in the correct textual form); that the order of the NFA's constituent parts are as in the example above (which by design corresponds with how the definition of a DFA is formulated); and empty string transitions will designated by a single underscore '_' (e.g., the triple ) _ A would represent an empty string transition from state ) to state A). Usage The program NFAConvert is intended to be run via the following command-line invocation: $ java NFAConver input.txt If no input file is specified or if the input file is not found, an appropriate error message must be displayed. For example: 1 $ java NFAConvert NFAConvert: no input file specified 2 3 4 $ java NFAConvert no-such-file.txt NFAConvert: the file 'no-such-file.txt' could not be opened 5 If a valid file is specified as input, then the output of the program will be the equivalent DFA in plain text form (using the same format as that input DFA). The DFA is to be obtained using the same algorithm discussed both in lecture and in the reading. As an example, using the file input.txt mentioned above, your program should behave as follows23. 2 3 4 5 6 7 $ java NFAConvert input.txt % 0 {A} {B} {C} {D} {E} {F} {G} {H} 8 9 10 2 Note that in the example output there is exactly one space between the string and its results. As before, line numbers are included for reference only. 3Recall that states of the resulting DFA are sets of states of the input NFA. As a consequence, the order of their elements is irrelevant. The same is true of those constituent parts of the DFA that are themselves sets. Furthermore, for simplicity, you may use square brackets instead of braces when converting sets to string form. 11 12 {I} {J} % Sigma 13 14 O 15 1 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 % F {A} {B} {C} {D} {E} {H} {I} % QO {A} % Delta {A} {B} {A} 1 {C} {B} {B} {B} 1 {E} {C} o {D} {C} 1 {C} {D} {B} {D} 1 {G} {E} o {F} {E} 1 {C} {F} o {B} {F} 1 {I} {G} o {H} {G} 1 {C} {H} {B} {H} 1 {J} {I} o {3} {I} 1 {C} {J} o {J} {J} 1 {3} 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 Compilation Notes Your program must compile using the following command-line invocation: 1 $ javac *.java Do not submit any IDE specific files and in the interest of simplicity do not use packages for this assignment. If your program does not compile using the command mentioned above you will receive no credit