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.

fibolapin-bw

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;
 }

*
* *

scisspares

Rabbit mitosis

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: