# String matching automata preprocessing

I have an alphabet A = {a,b,c} and a pattern P = "abcaab".

The task is to build a finite automaton of the transition function (delta) for {0,6} (the length of the pattern) and each element of the alphabet A.

My incorrect solution:

New correct solution:

I've highlighted the field that I am having trouble with in yellow. States run along the top and my alphabet along the side.

Although I believe my solution is correct I don't understand how that field is calculated.

The rest seem obvious since if there isn't a match return to the initial state 0. If 'a' is the next input return to 1 unless in states 3 or 4. However whilst in the accepting state if the next input is 'b' I need to return to state 2.

I know this is because 'a' is guaranteed to before the 'b' otherwise state 6 would not have been reached. What I don't know however is how this is pre-calculated in the COMPUTE-TRANSITION-FUNCTION algorithm.

More details can be found on page 996-1002 of Introduction to Algorithms Third Edition.

I used the table above to match strings in the following text:

-
I can't say anything about the part of the question that refers to a book I don't have. (The Google Books preview doesn't contain those pages.) Concerning your argument "I know this is because 'a' is guaranteed to before the 'b' otherwise state 6 would not have been reached." -- that's not true; state $6$ was reached by encountering a 'b', so this is the second 'b', and as far as I can tell it should put you back to state $0$ since there's no occurrence of two 'b's in the pattern. On the other hand, a 'c' should put you into state $3$, since it implies you just saw "abc". – joriki Dec 10 '11 at 23:08
But the first 2 characters are a suffix of the pattern. If I went back to the initial state I'd potentially miss string matches. – Ash Dec 10 '11 at 23:33
I don't understand that comment. I was talking about just that, how to handle the fact that the first two and last two characters coincide. If you encounter a 'b' after a complete match, you can't miss any matches by going back to the initial state, since there are no matches that contain "bb". The table you've added in the meantime supports what I was saying: You need a $3$ in the 'c' row in the last column, since a 'c' after a complete match means you've just encountered "abc". Using your table, you'd end up in state $0$ instead and would miss the second match at position $7$. – joriki Dec 11 '11 at 0:31
Yes I have discovered that this was my error. I was, as you say, including an extra b instead of adding a c to the suffix of the string. – Ash Dec 11 '11 at 0:34
I skimmed your initial comment and missed the point. My apologies for the confusion. – Ash Dec 11 '11 at 0:39

It might be easiest to think of this as minimizing a NFA that recognizes .*abcaab. The NFA has one state for each position in the search string you could have reached yet, and the states in your DFA will consist of sets of the NFA states. By coincidence (because you're only searching for a fixed string) each of the DFA states can be identified by the highest NFA state it contains, and you'll then only need to keep track of which other states you could also have reached.

Thus, in your state 4 you have already seen something that ends with abca, but that really mean that what you have seen so far ends with abca and a both. So If you see an a in this situation you move to state 5 (abcaa), but if you see a b in state 4, you need to discard abca and work on the NFA state b. So a b in state 4 should lead to state 2 rather than to state 0. Otherwise you won't find the match in abcabcaaba.

Also, if you get to state 6 you have already seen all of abcaab. If you move to state 2 for a b in this situation you will have seen abcaabb with two bs at the end, which is not what state 2 expects. Is that a typo in your transition table? I notice that your example moves to state 3 rather than state 2 here.

Depending on exactly how your automaton formalism works, I suspect that you don't actually want to have a state 6 at all. Instead seeing a b in state 5 should accept and move to state 2 because once you have matched abcaab you still have an ab at the end that could be the start of yet another match.

Alternatively, you might want to move to state 6 and have state 6 be an accepting state with exactly the same transitions out of it as for state 2.

-
State 6 is an accepting state. I know that doesn't appear to be clear from my question. – Ash Dec 11 '11 at 0:36
Regarding the last sentence: Yes, those are the transitions I suggested in my comment. Regarding the example: It moves to state $3$ upon encountering a 'c', not a 'b'; this is what it should do, but not what the first table would tell it to do. – joriki Dec 11 '11 at 0:37
@Ash, I thought that maybe your formalism said that a yellow background in the table meant an accepting transition or something. An accepting state is indeed the more common way to do it. – Henning Makholm Dec 11 '11 at 0:47
I was just trying to draw people's attention to that cell. Thank you Henning. – Ash Dec 11 '11 at 0:49
@Ash, your edited solution is still missing the $4\to2$ transition on b. – Henning Makholm Dec 11 '11 at 0:51

Figures are a log easier to look at then a table when analyzing finite automata's. I have taken the liberty of constructing the automata given into something more recognizable:

Where state 0 and 6 are start and accepting states, respectively and all unlabeled transitions go back to state 0.

My version of Cormen, Leiserson and Rivest is older than yours (the algorithm you reference is on page 868 in mine) but I believe the content is the same. Here is the algorithm they present:

$\text{Compute-Transition-Function}(P, \Sigma)$
1 $\ \ \ \ m \leftarrow length[P]$
2$\ \ \ \ {\bf \text{for } } q \leftarrow 0 {\bf \text{ to }} m$
3$\ \ \ \ \ \ \ \ {\bf \text{do for }} \text{each character } a \in \Sigma$
4$\ \ \ \ \ \ \ \ \ \ \ \ {\bf \text{do }} k \leftarrow \text{min}(m+1, q+2)$
5$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\bf \text{repeat }} k \leftarrow k - 1$
6$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ {\bf \text{until }} P_k \sqsupset P_q a$
7$\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \delta(q,a) \leftarrow k$
8$\ \ \ \ {\bf \text{return }} \delta$

They want to construct a DFA of length one longer than the pattern, $P$. The state transition is stored in $\delta$. $\delta(q,a) \leftarrow k$ adds an edge with label $a$ from state $q$ to state $k$. They loop through each state and for each state loop through each character in the alphabet to determine where that state should go.

I believe the problem you are having is with the suffix function on line 6, where the suffix function is '$\sqsupset$'.

The suffix function is defined as follows:

$w \sqsupset x \rightarrow \exists y \ \text{ s.t. } x = yw$

meaning, $w$ can be found as a suffix of $x$.

In words, the loop that line 6 is contained in is saying "Find the maximum suffix of the strings shorter than the current state $q$ that start at $P[0]$". Once that is found, we know we can 'skip ahead' and transition to that state instead of the beginning. There are some fence post issues and that's why they have the min function there, but the intuition still holds.

By considering all strings, $P_k$, that start at the beginning of the pattern shorter than the current position of the read pattern, $P_q a$, we test each $P_k$ to be a suffix of $P_q a$ and choose the maximum. This is just a more formal and generalized way of expressing your intuition.

-
I've upvoted your answer but your DFA misses the 4 -> 2 transition on 'b' input that @HenningMakholm pointed out. – Ash Dec 12 '11 at 1:12
@Ash, fixed, thank you – user4143 Dec 12 '11 at 1:24
Can I ask what program you used to create that DFA diagram? – Ash Dec 12 '11 at 13:29
@Ash, graphviz. I'm happy to provide source but the dot file is pretty basic – user4143 Dec 12 '11 at 16:04