Introduction to the Theory of Computation:Sipser Introduction to the Theory of Computation 3rd Edition
Theorem 1.39 on Page 55 of textbook [Introduction to the Theory of Computation:Sipser Introduction to the Theory of Computation 3rd Edition] says that every NFA has an equivalent DFA, followed by the construction
procedures of equivalent DFA given a NFA. In this project, will write a program using Using Java Programming to implement part of such construction procedures.
Read part of the transition table of a NFA from a txt file, suppose this table only contains two columns: the first
column lists out the states, while the second column lists out what each state jumps to upon the input e. For
example, given the following transition table in a txt file:
1,{2, 3}
2,empty 3,{4}
4,empty
We know the corresponding NFA contains the following set of states: 1, 2, 3, 4 . Also state 1 jumps to states 2,
3 upon the input of ε, while state 2 does not have an outgoing arrowhead with ε on, namely it jumps to ∅ upon the input of ε (in the txt file we use “empty” to denote empty set ∅).
Read part of the transition table of a NFA from a txt file, and then print out the set of states the equivalent DFA has and E(q) for each q in the set of states of the NFA. For example, for the above part of the transition table of a NFA, the print out should be
State set of the equivalent DFA = {empty, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2,
3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}
E(1) = {1,2,3,4}
E(2) = {2}
E(3) = {3,4}
E(4) = {4}
Note that your program must be able to work for any input, not only just for the above given example.
The following are a few more examples you can use to test your program (I highly recommend that you come up with more examples to make sure the correctness of your program):
(1) 1,{3}
2,empty 3,empty
For the above part of the transition table of a NFA, the print out should be
State set of the equivalent DFA = {empty, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
E(1) = {1,3}
E(2) = {2}
E(3) = {3}
(2) 1,{3}
2,{1}
3,empty
For the above part of the transition table of a NFA, the print out should be
State set of the equivalent DFA = {empty, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}
E(1) = {1,3}
E(2) = {1,2,3}
E(3) = {3}
(3) 1,{2,3}
2,empty 3,{4,5}
4,empty 5,empty
For the above part of the transition table of a NFA, the print out should be
State set of the equivalent DFA = {empty, {1}, {2}, {3}, {4}, {5}, {1, 2}, {1, 3}, {2, 3}, {1, 4}, {2, 4}, {3,
4}, {1, 5}, {2, 5}, {3, 5}, {4, 5}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 5}, {1, 3, 5}, {2, 3, 5}, {1,
4, 5}, {2, 4, 5}, {3, 4, 5}, {1, 2, 3, 4}, {1, 2, 3, 5}, {1, 2, 4, 5}, {1, 3, 4, 5}, {2, 3, 4, 5}, {1, 2, 3, 4, 5}}
E(1) = {1, 2, 3, 4, 5}
E(2) = {2}
E(3) = {3, 4, 5}
E(4) = {4}
E(5) = {5}
– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
Example:
1,{2, 3}
2,empty
3,{4}
4,empty
– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
Test 1:
1,{3}
2,empty
3,empty
– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
Test 2:
1,{3}
2,{1}
3,empty
– – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – – –
Test 3:
1,{2,3}
2,empty
3,{4,5}
4,empty
5,empty
