Assignment: NFA to DFA with Python Before starting the work on this assignment, you should view the video lecture explaining each of the algorithms and implementation details. The links to the video lectures are in the NFA.Implementation.StreamingVideoLinks.pdf file available on Moodle. You are also recommended to read Chapter 6 by Webber (available on Moodle as well) You should submit a zipped "dfa.nfa python" folder containing the subfolders for each of the two algorithms. Learning Objectives: Here you are to implement an NFA below via two different algorithms discussed in the lecture: (1) recursive backtracking search and (2) bit-mapped parallel search Use the example code (available for download on Moodle) and modify it to support the NFA given below You will also be tasked with the job of comparing runtimes of these algorithms on different size strings for the NFA depicted below. Edit the main method of the "Filter.py files in the example code to report a runtime after all lines have been processed. To measure time, you can use the time package in python. You will need to create a large list of strings that can be tested as input (since processing only one string will not provide meaningful runtime results). Place a large list of strings in a file, with one string on each line. Then, you can run all the strings by redirecting stdin from this file like: python NFA1Filter.py stringlist.txt Make a plot where the x-axis is the size of the strings and the y-axis is the runtime. Rather than having each point represent the runtime per one string (since this will be astronomically low), make the y-axis the runtime per N number of strings. Make N large enough to get meaningful results. Experiment with the methods and analyze your results: try to answer some of the following questions: l. Is one method consistently better than the other? 2. Why do you believe to be or not to be the case? 3. Are there different types of input that would benefit one method over another. For example does one method reject faster than the other? Does one work better with small strings? Etc Note: You should make the plot using Python. The following is some idea of how you might do it in Python, and of course, you can do it in different ways: mac import matplotlib.pyplot as plt bitmap, #plt.plot ([1,2.31, label+ bitmap) backtrack, + pit.plot [3.2.il. label backtrack) pit.legend(handles [bitmap, backtrackl) plt.ylabel ( run time ) plt xlabel (inputs processed) plt.showl) Submission Instructions acer