Construct the string-matching automaton for the pattern P = aabab and illustrate its operation on the text string T = aaababaabaababaab.
run my program FA.c you will get the answer.
Draw a state-transition diagram for a string-matching automaton for the pattern ababbabbababbababbabb over the alphabet Σ = {a, b}.
run my program FA.c then you can draw the diagram.
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.
这样子的模式产生的要么指向下一个状态,要么重新回到状态0.
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.
UNSOLVED
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|.
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.