next up previous

Exercise 11: The fundamental concepts of LFGs.

Consider the Fibonacci generator .

(a) Draw a shift register diagram, similar to Figure 10, to represent , the action of this generator.

(b) How long is the period, P, of this generator?

(c) How many distinct cycles does this generator have?

(d) Using the information for this generator in Table 4, initialize, in canonical form, every cycle for this generator, and generate each full cycle.

(e) Suppose the generator were initialized with the values, , , and . If the generator were advanced for a full cycle, which of the ``canonical'' cycles generated in part (d) would be the same as this new one? How many advances of the generator did you need to determine this?

(f) Would parts (a) through (e) be fun to do if the generator changed only slightly, from to ? What is the value of P for ? How many distinct cycles does it have?