Answer Happy

II. String-matching automata (50 points) Given the following string text: Petri wrote Petri net. Given a pattern: Petri net 4. (10 points) Apply the brute-force string matching algorithm to determine whether it is occurred in the given string text. How many times of comparison between the contents of the pattern and the text do you need to have? (You need to show the number of comparisons you have claimed.) 5. (30 points) Given a pattern P which is Petri net, let restrict input alphabet Σ = {space, e, i, n, o, p, r, t, w, .). Construct a finite automaton matcher. Construct a finite automaton for string matching. Use this finite automaton to determine whether the given pattern "Petri net" is appeared in any texts. For this problem, based on the given pattern and rejecting otherwise, you need to construct a (states vs inputCharacters) table for accepting the given pattern. Then from this table, construct the string-matching automaton (i.e., the state transition diagram) for recognizing the given pattern. inputCharacters e i 0 P r t W Pattern P t r 1 state 0 1 2 3 4 5 6 7 8 t 9 6. (10 points) Give the time efficiency and space efficiency for the problem 4 (brute force string matching) and problem 5 (finite automaton matcher)? n