NFA to DFA

Write a Java program to convert any given NFA to an equivalent DFA. NFA files is shown in the following example: 3 a b c d 0: {0} {0,1} {} {} {1,2,0} 1: {} {1} {1} {1} {1} 2: {} {1,2} {1} {1} {2} 0 {1,2} • The first line contains the number of states of the NFA; in this case, there are 3 states. • The second line contains Σ = {a, b, c, d}. • After that, each line is a state and its transition. The number to the left of the colon is the label of the state. After the colon, each set is the set of next states on the input alphabet corresponding to the alphabets in Σ in the same order as shown in the second line plus the λ-transition at the end of the same line. For example, the transitions of the NFA shown above from state 0 are: δ(0, a) = {0}, δ(0, b) = {0, 1}, δ(0, c) = {}, δ(0, d) = {}, and δ(0, λ) = {0, 1, 2}. Note that, the last column is referred to λ-transition, and coming back to self is always implied; therefore, 0 is included in δ(0, λ) = {0, 1, 2}, although 0 may not be shown in the last column of state 0. • After every state’s transitions are specified, there is a line to indicate the starting state. In this case, 0 is the starting state. • The last line contains the set of final states. In this case, {1, 2} I will compile and run the program from the Unix command line as follows: javac [login to view URL] java NFA nfa2 [login to view URL] the program should print out the following text: (1) The original NFA (2) An equivalent DFA (no need to minimized) (3) The list of strings in [login to view URL] that are accepted by the NFA (don’t list those that are rejected). Here is the example output: Sigma:a b ------ 0: (a,{1}) (b,{4}) ( ,{2}) 1: (a,{5}) (b,{2}) ( ,{}) 2: (a,{5}) (b,{}) ( ,{}) 3: (a,{}) (b,{}) ( ,{0}) 4: (a,{}) (b,{1}) ( ,{3}) 5: (a,{}) (b,{}) ( ,{4}) ------ 0: Initial State 5: Accepting State(s) To DFA: Sigma: a b ------------------ 0: 1 2 1: 1 3 2: 1 3 3: 1 3 ------------------ 0: Initial State 1: Accepting State(s) The following strings are accepted: aabaa aaaaa