In my discrete mathematics class, I often use the Fibonacci rabbits example, here to show how to resolve a recurrence, there a variant where some rabbits go away, here again for rewrite systems.

What are rewrite systems? Not unlike context-free grammars, they provide rules generate “words” in a “language”. Turns out the Fibonacci rabbit population problem is super-easy to model as a rewrite system.

The Fibonacci rabbit problems asks how many rabbits you have after a given number of generations, stating with a juvenile couple, that takes 1 generation to mature, then produce a couple of offsprings that also takes 1 generation before reproducing of their own. The classical form of the recurrence that solves the problem is given by:

If we want to generate the populations (and not just their number), we must use something like a rewrite system, we get the rules:

This, starting with J, gives:

1 J 1 M 2 MJ 3 MJM 5 MJMMJ 8 MJMMJMJM 13 MJMMJMJMMJMMJ 21 MJMMJMJMMJMMJMJMMJMJM 34 MJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMMJ 55 MJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMJM 89 MJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMMJMJMMJMJMMJMMJMJMMJMMJ ...

Here we assume that between generations *all* symbols are replaced according to the rule, from left to right.

*

* *

The rabbits problem, as traditionally formulated, supposes that the rabbits are immortal. What if some of them die? Say after 5 generations? If we say that the rabbits live to be 5 generations old, we get the following rewrite rules:

Where symbolizes the empty string (basically erasing the symbol). We then get the following populations:

1 1 1 2 2 31 3 412 5 51231 6 231412 10 3141251231 14 41251231231412 21 512312314123141251231 30 231412314125123141251231231412 45 314125123141251231231412512312314123141251231 ...

There are other variations… what if we say the rabbits don’t get to live their fourth generation? The rewrite rules become

and the sequences becomes

1 1 1 2 2 31 3 412 4 1231 6 231412 9 314121231 13 4121231231412 19 1231231412314121231 28 2314123141212314121231231412 41 31412123141212312314121231231412314121231 ...

*

* *

Implementing a rewrite system like that is really not that complicated if we restrain non terminals symbols to be single characters (it removes possible ambiguity and spares us the trouble of writing a parser). A quick (C++ 2011) implementation gives something like this:

#include <map> #include <string> #include <iostream> #include <iomanip> typedef std::map<char,const std::string> rules; std::string next(const std::string & prev, const rules & r) { std::string result; for (char p : prev) { // hack to ensure const-ness on rules rules::const_iterator x=r.find(p); if (x!=r.end()) result+=x->second; else result+='X'; // oh noes! } return result; } int main() { // rules for the classic problem static const rules immortal{ {'1',"2"}, {'2',"21"} }; // rules if the rabbits die when they turn 5 static const rules mortal1{ {'1',"2"}, {'2',"31"}, {'3',"41"}, {'4',"1"} }; // rules if the rabbits die when they turn 6 // and lived to be 5 a whole generation. static const rules mortal2{ {'1',"2"}, {'2',"31"}, {'3',"41"}, {'4',"51"}, {'5',""} }; std::string population="1"; for (int i=0;i<15;i++) { std::cout << std::setw(3) << population.size() << " " << population << std::endl; population=next(population,immortal); } return 0; }

*

* *

Rabbit mitosis