A string over I is an input string for M. If there are states s1,...,sn S with s0 = s0 sk = f (sk-1, xk) for k = 1,..., n; and yk = g (sk-1, xk) for k = 1,..., n, the string y1...yn is the output string for M corresponding to the input string x1...xn.