P14.7.9 Here is an optimization problem that we can solve with the aid of an ordinary NFA and another technique from Chapter 9. We are given a finite set S of nonempty words over 2, and a string w of length n over E. We would like to find non-overlapping occurrences of words in S within w, to use as many as possible of the letters in w. We are allowed to use the same word in S multiple times if that is best. (a) Build an ordinary NFA N, with one final state that is also the start state, such that an accepting w-path corresponds to a set of non-overlapping occurrences of words from S within w. (b) In Chapter 9 we learned uniform-cost search, which finds the shortest path from one node to another in a labeled directed graph. Construct a labeled directed graph G from N, with one final state f, such that any path from the start state to f corresponds to a set of non-overlapping occurrences of words from S in w, and the cost of that path is 2n-m, where m is the number of letters of w used by the words from S. (Hint: Make G from n + 1 copies of N.) (c) Explain how, using uniform-cost search, we can find the optimal set of word occurrences. Note that UCS finds paths of minimum cost, while we want paths of maximum value.