Please write the following program in python.

2 Matcher Write a function that tests whether a NFA M accepts a string w : match(M,w) - M : An NFA to run - w : The string to run on - Returns: A pair (flag, path), where - flag: True if M accepts w; false otherwise. - path: List of the transitions on an accepting path. If there is more than one, an arbitrary path is returned. This function is required to be linear both in the length of w and the number of transitions in M. Here's how to do this. Define a configuration of M on input string w to be a pair (q,i), where qQ and 0iw. These configurations can be thought of as nodes in a graph. For example, if the NFA is N1 above and w=010110, then the graph of configurations would be: This is similar to Sipser's Figure 1.29, but there are several differences here. The most important difference is that configuration (q4,5) appears only once with two incoming edges, instead of appearing twice. In general, each configuration appears at most once in the graph. As a result, the graph has at most Qw+1 nodes and w edges. Then, deciding whether N1 accepts w amounts to searching for a path from the start configuration (in this case, (q1,0) ) to an accept configuration (in this case, (q4,6) ). You can use any graph search algorithm; breadth-first search is probably the least hassle, but depth-first search corresponds to how the real Unix tools work. (One particular thing to watch out for is cycles of -transitions, as in cycle.nfa. Make sure your matcher doesn't hang when it encounters one.) When you studied graph search algorithms, you may not have seen how to reconstruct the found path. Graph searches maintain a set that keeps track of which configurations have been visited. If you change this to a data structure that records, for each configuration, how you got to that configuration, then after the search finishes, you can use that information to reconstruct the path