Again we make use of your PrefixToTree class from the first phase. However, now we are also using a TreeToNFA classfrom the second phase. And finally, we are using the NFAToDFA class that you have to write for this phase. The NFAToDFA class supports new and to_dfa . The question again arises of how to test that the DFA produced is correct. The approach taken here is the same as was taken to test the NFA from phase 2, i.e., to use it to try and see if various regular expressions match various strings. This is done by a class DFAScanner which I write (in app/phase_3_helpers.rb). The implementation of DFAScanner provided, imposes further constraints on how NFAToDFA works. DFAScanner looks like:
as you can see, DFAScanner is simpler than NFAScanner was (since there is no backtracking in the DFA).
Looking at the code to DFAScanner, we find that the object to_dfa returns must meet the requirements:
R. a DFA accepts message start and returns something I will refer to as a state (see method match)
S. a state must accept the accepting? message (see method accepting?)
U. a DFA accepts the message next with parameters state and category to return something that is either a state or the class NullState
V. there is a class named NullState that is defined and exists for the sole purpose of having something to return when there is not a transition from the current state on the current input character according to the method next.
In addition to this `type information’, there is the overall semantic constraint that if these various messages are implemented correctly, then the match method in my DFAScanner class should be able to correctly determine from the DFA whether or not the DFA would match a particular string (with the answer being the same as would be expected from the question of whether or not the original regular expression would match that same string).
As with the first and second phases, the test data that will be used to evaluate the correctness of your solution will not be limited to that that appears in app/phase_3_sample_tests.rb .
