I'm just starting to read TAOCP Volume 1 and I'm having trouble understanding the style.
Knuth mentions a computational method to be a quadruple (Q,I, Omega, f) -- but I am having trouble understanding what each of these is intended to be. I understand his first example, but don't understand his second
I'm looking at page 8 of the third edition.
Near the end of the chapter there is an algorithm that talks about sets of strings.
(I have replaced Greek variables with some easier to type ones -- sorry)
Let A be a finite set of letters, and let A* be the set of all string on A. The idea is to encode the states of the computation so that they are represented by strings of A*
Q = (s,j) where s is in A* and j is an integer, 0 <= j <= N
I = subset of Q with j = 0
Omega = subset with j = N
f = function below
(note that p & w are strings) If and s are strings in A*, we say that T occurs in s if s has the form pTw for strings p and w.
f(s,j) = (s,aj) if Tj does not occur in s; f(s,j) = (pYjw,bj) if p is the shortest possible string for which s = pYjw f(s,N) = (s,N)
I understand the concept of making sets of strings, but don't understand all that he is trying to say here. Why do I need Q, I, Omega? What is the f really explaining to me (why do I need 3 functions in f?)??
Can anyone help shed some light?
Q = set of states (so that (s, j) represents state s at time j)
I = initial states (hence the requirement that j == 0)
Omega = final states (hence the requirement that j == N)
f = transition function
Also, there aren't three functions named f but rather f is piecewise-defined by three equations.