Nfa to Dfa java program

Write a Java program named NFA2DFA.java that will convert any given NFA from a text file in the format described as follows to an equivalent DFA and minimized it. The two DFA’s created by your program, before and after minimization, will both be used to parse strings in a text file. Your programs will be compiled, run, and graded on our Unix system.

NFA file format: An NFA is prepared in a text file with the following format: Consider file X.nfa

• The first line contains the number of states of the NFA; in this case, there are 5 states, indexed from 0 to 4.

• The second line contains Σ = {a, b, c, d}. • Starting from the third line, each line is a state and its transition, where the number followed by a

colon is the index, and after the colon, each set is the set of next states on the input alphabet corresponding to alphabets in the second line plus the λ-transition at the end of the same line.

For example, consider q4 of X.nfa above. We have: δ(q4,a) = {q3},δ(q4,b) = {},δ(q4,c) = {q1}, δ(q4, d) = {q3, q4}, and δ(q4, λ) = {q0, q2, q4}.

Note that, the last set is referred to the λ-transition, and it always contains state itself, i.e., q0 is included in δ(q0, λ); likewise q1 ∈ δ(q1, λ) and q2 ∈ δ(q2, λ), and so on.

• After every state’s transitions are specified, there is a line to indicate the starting state. In this example, 3 indicates that q3 is the starting state. (Note, the starting state may not be q0.)

• The last line contains the set of final states. In this example, {q3,q4}

• Name your main program as NFA2DFA.java that will take two command line arguments. I will compile and run your program from the Unix command line as follows:

javac NFA2DFA.java java NFA2DFA X.nfa strings.txt

The first argument is an NFA file as the aforementioned X.nfa, and the second argument is the file of input strings. Your program should check every string in strings.txt (including an empty string) and print Yes or No on the screen to indicate whether input NFA accepts the string. Your program will not parse the input string using the NFA directly, which is rather inefficient since we have to rely on back-tracking. Instead, the NFA should be converted an equivalent DFA and use the DFA to parse every string in strings.txt. The output of your program should include the following information on the screen:

(1) An equivalent DFA (no need to be minimized at this stage) in the following format.

(2) A list of answers of the DFA on the strings in strings.txt. There are 30 strings in strings.txt. Arrange your program to show exactly 15 answers in a line on the screen.

Then, your program should move on and minimize the DFA and use the minimized DFA to parse the same string file and print the minimized DFA and parsing results as follows:

As you can see, before and after minimization, the parsing results should be consistent.