Art of Computer programming notation 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?

From stackoverflow

• I'll hazard a guess since I don't have the book with me right now:

  I = initial state(s)
  

  Q = transition function Omega = final state(s)But as I said, I only hazarded a guess ;)

  Nicholas Mancuso : close but not quite there.

• 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.

  Nicholas Mancuso : damn you just beat me! +1.

  Hortitude : I guess what I might be missing is how the 3 pieceswise functions achieve the overall goal?

• 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?

  Hortitude : If I could have marked two answers as accepted I would have -- thanks for your help!