Art of Computer programming notation question

Question

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?

Answer 1

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.

Answer 2

I'm not 100% sure, but it looks like Q is the set of all ordered pairs (s, j) for 0 <= J <= N. This will be your domain. It is the set of all possible states given some N and string s.

I is your subset of Q where all ordered pairs contain J=0, or your initial states. Omega is your subset of Q where all ordered pairs contain J=N, or your final states.

f is the actual function over domain Q.

EDIT

Think of the function definition being something along the lines of one function, but different cases depending on the given input. Think of a function you would writing in a language. ex:

tuple f(string s, int i)
{
    if (Tj not in s)
        (s, aj)
    else if ( p is shortest possible length such that s = pYjw)
        (pYjw,bj)
    else if ( i == N )
        (s, N)
}

Another example is the Fibonacci function definition. See how that is defined? Make sense?