## Fibonacci rabbits as a rewrite system

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:

\begin{aligned} F_1&=1\\ F_2&=2\\ F_n&=F_{n-1}+F_{n-2} \end{aligned}

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

\begin{aligned} \text{start}&\to J\\ J&\to M\\ M&\to MJ \end{aligned}

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:

\begin{aligned} \text{start}&\to 1\\ 1&\to 2\\ 2&\to 31\\ 3&\to 41\\ 4&\to 51\\ 5&\to \perp\\ \end{aligned}

Where $\perp$ 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

\begin{aligned} \text{start}&\to 1\\ 1&\to 2\\ 2&\to 31\\ 3&\to 41\\ 4&\to 1\\ \end{aligned}

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