The goal of this homework is to understand DFAs and NFAs by implementing them in Python. I provide a partial implementation and a test suite. Your job is to fill in the missing methods so that all tests pass.
Before starting this homework, you should have read Sipser's Chapter 1, especially pages 44-63.
DFA
1) Download dfa.py and dfa_test.py. Spend some time reading the code before you start working with it. Really.
2) If you run dfa_test.py, one test should pass and two should fail.
3) Fill in the body of DFA.union using the algorithm in Sipser's Theorem 1.25.
4) Debug until all tests pass.
NFA
1) Download nfa.py and nfa_test.py. Again, spend some time reading the code.
2) If you run nfa_test.py, one test should pass and three should fail.
3) Fill in the body of NFA.union using the algorithm in Theorem 1.46. Note: don't use DFA.union.
3) Fill in the body of NFA.concat using the algorithm in Theorem 1.48.
3) Fill in the body of NFA.star using the algorithm in Theorem 1.50.
4) Debug until all tests pass.
NFA->DFA
Optional question for extra challenge: write a function called make_dfa_from_nfa that takes an NFA object and constructs the equivalent DFA using the algorithm in Theorem 1.39.
Hint: the structure is similar to NFA.process().