It’s been a while since I posted because I went on vacation and the material got hard at the same time. Not a motivating combination!

Anyway, I spent an awful lot of time struggling to understand the so called “failure function.” This is actually hidden in an exercise to section 3.4 and not expounded upon much in the main text, but it’s pretty interesting. The text explanation is

The objective is that b1b2…bf(s) is the longest proper prefix of b1b2…bs that is also a suffix of b1b2…bs

where the f in bf(s) is the failure function. This took me some time to understand; I’ll try to walk through an example.

Consider the keyword ababaa (the example given in the book). Then b1 = a, b2 = b, etc. So f(1) = 0 because there is no proper prefix of a 1-character string. f(2) = 0 because the only proper prefix of ab is a, which is not a suffix of ab. The proper prefixes of aba are a and ab. a is also a suffix of aba, so f(3) = 1. And so on.

The algorithm given for calculating the failure function is not immediately clear in its relation to the failure function, but it works as advertised. An implementation is up on the github.

Most of the exercises here are either manual and tedious and thus omitted, or else rigorous and difficult, and thus omitted. I am not interested in providing rigorous proofs, so once I got through enough of the problem to be satisfied that I understood it, I quit refining.

Section 3.5 is about Lex, which is sort of an insane detour as far as I’m concerned. Exercises omitted. 3.6 coming up soon!