Example 3.1.6. Consider the “unit delay” function f: {0, 1}* _ {0, 1}* defined by f(_) = _, and f(_1_2 … _k) = _1_2 …__k-1 for kŤ1, and _i___ (1ŠiŠk). Clearly f is extendible.
For x,y___* and y ° _, f(0y) = 0f(y) = f(0)f0(y) = f0(y) and so f0(y) = 0f(y). Also f(x0y) = x0f(y) = f(x0)fx0(y) = xfx0(y) implies that fx0(y) = 0f(y). Finally since f(0 _) = _ = _ _ = f(0) _, f0(_) = _. Similarly fx0(_) = _. Hence we see that fx0 = f0 for all x___*
Similar analysis shows that fx1 = f1 for all x___*. Since f(01) = 0 and f(11) = 1, f0(1) = 0 while f1(1) =1, and therefore f0 ° f1.
Finally note that f(_y) = f(y) = _f(y), so f_ = f (and f_(1) = _). Hence there are three distinct derived functions {f_, f0, f1}, so f has index 3.
| Previous slide | Next slide | Back to first slide | View graphic version |