Reber grammar strings (named after Arthur S. Reber) are strings often used to test if a software system can recognize patterns. Two examples of Reber strings are “BTSXSE” and “BPTTVPXVVE”.

How Reber strings are generated is best explained using a diagram:

The string must start with a ‘B’ (“begin”) symbol. Next can be either a ‘T’ or a ‘P’. If the second symbol is a ‘T”, the third symbol can be an ‘S’ or an ‘X’. The process continues until an ‘E’ (“end”) is reached.

I wanted to programmatically generate Reber strings so I wrote a short C# program to do so. I used the program to find all possible Reber strings that have exactly 8 symbols. I used brute force: I generated 100 million random Reber strings and tracked which of them had exactly 8 characters. There are 7 such strings:

1. BTSSSXSE
2. BPTTTVVE
3. BTXXVPSE
4. BPTTVPSE
5. BPVPXVVE
6. BTSXXVVE
7. BTXXTVVE

I ran the program looking for Reber strings that have exactly 20 symbols and got 783 strings:

Begin Reber Grammar demo

Found 783 distinct Reber strings with length = 20 symbols
1    BPVPXTTTTVPXVPXTTVVE
2    BTSSXXTVPXTTTTTTVPSE
3    BTSSSSXXTTTVPXTTVPSE
4    BPTTTTVPXTVPXVPXVPSE
. . .
782  BTSSSXXTTTVPXTTTVPSE
783  BTXXTTTTTTTTTTTTVPSE

The program code for the 8-symbol strings is:

using System;
using System.Collections.Generic;

namespace ReberGrammar
{
  class Program
  {
    static Random rnd = new Random(0);

    static void Main(string[] args)
    {
      Console.WriteLine("\nBegin Reber Grammar demo\n");

      Dictionary<string, bool> dict =
        new Dictionary<string, bool>();

      for (int i = 0; i < 100000000; ++i)
      {
        string reber = Reber();
        if (reber.Length != 8) continue; // only length 8
        
        if (dict.ContainsKey(reber) == false)
        {
          dict.Add(reber, true);
        }
      }

      Console.WriteLine("Found " + dict.Count +
        " distinct Reber strings");

      int id = 0;
      foreach (string rs in dict.Keys)
      {
        Console.WriteLine(id + " " + rs);
        ++id;
      }

      Console.WriteLine("\nDone\n");
      Console.ReadLine();

    } // Main

    static string Reber()
    {
      return DoNode0("B");
    }

    static string DoNode0(string curr)
    {
      double p = rnd.NextDouble();
      if (p < 0.5) { return DoNode1(curr + 'T'); }
      else { return DoNode2(curr + 'P'); }
    }

    static string DoNode1(string curr)
    {
      double p = rnd.NextDouble();
      if (p < 0.5) { return DoNode1(curr + 'S'); }
      else { return DoNode3(curr + 'X'); }
    }

    static string DoNode2(string curr)
    {
      double p = rnd.NextDouble();
      if (p < 0.5) { return DoNode2(curr + 'T'); }
      else { return DoNode4(curr + 'V'); }
    }

    static string DoNode3(string curr)
    {
      double p = rnd.NextDouble();
      if (p < 0.5) { return DoNode2(curr + 'X'); }
      else { return DoNode5(curr + 'S'); }
    }

    static string DoNode4(string curr)
    {
      double p = rnd.NextDouble();
      if (p < 0.5) { return DoNode3(curr + 'P'); }
      else { return DoNode5(curr + 'V'); }
    }

    static string DoNode5(string curr)
    {
      return curr + 'E';
    }

  } // Program
} // ns

Reber strings cannot be recognized by regular neural networks, but a special form of NN called a recurrent neural network can learn to recognize Reber strings.