32.3.md

Exercises 32.3-1

---

Construct the string-matching automaton for the pattern P = aabab and illustrate its operation on the text string T = aaababaabaababaab.

Answer

run my program FA.c you will get the answer.

Exercises 32.3-2

---

Draw a state-transition diagram for a string-matching automaton for the pattern ababbabbababbababbabb over the alphabet Σ = {a, b}.

Answer

run my program FA.c then you can draw the diagram.

Exercises 32.3-3

---

We call a pattern P nonoverlappable if Pk ⊐ Pq implies k = 0 or k = q. Describe the state- transition diagram of the string-matching automaton for a nonoverlappable pattern.

Answer

这样子的模式产生的要么指向下一个状态,要么重新回到状态0.

Exercises 32.3-4 *

---

Given two patterns P and P′, describe how to construct a finite automaton that determines all occurrences of either pattern. Try to minimize the number of states in your automaton.

Answer

UNSOLVED

Exercises 32.3-5

---

Given a pattern P containing gap characters (see Exercise 32.1-4), show how to build a finite automaton that can find an occurrence of P in a text T in O(n) matching time, where n = |T|.

Answer

We can construct the finite automaton corresponding to a pattern P using the same idea as in exercise 32.1−4. Partition P into substrings P1, . . . , Pk determined by the gap characters. Construct finite automatons for each Pi and combine sequentially, i.e., the accepting state of Pi, i ∈ [1, k) is no longer accepting but has a single transition to Pi+1.

---

Follow @louis1992 on github to help finish this task