Regular expression for words where the same symbol can repeat at most two times consecutively?

Question

Having the alphabet $\{a, b\}$, how can I generate a regular expression for the language that does not have substring of three or more consecutive same symbol?

For example, I can't have ${baaab}$ nor ${abbba}$, but I can have ${abbaabba}$.

Answer 1

Every string over $\{a,b\}$ can be decomposed into runs of the same letter. For example, $$ abbaabba = a^1 b^2 a^2 b^2 a. $$ Since the alphabet is binary, the runs just alternate between the two letter. In your case, every run has length 1 or 2. We can distinguish between four types of words in your language, depending on which run is first and which run is last; additionally there are some corner cases. The set of words in your language in which the first run is $a$s and the last run is $b$s corresponds to the regular expression $((a+aa)(b+bb))^+$.

I'll let you figure out the rest.

Answer 2

How about this C++ code?

string loc;
char sent[] = {a, b};    
for (int i=0; i<N; i++)
{
   int pos = rand()%2;
   if (i>=2)
   {
      if (loc[i-2]==loc[i-1])
      {
         if (sent[i-2] == loc[i-1)
           loc.push_back(sent[!loc[i-1]]);
         else
           loc.push_back(sent[loc[i-1]]);
      }
      else
        loc.push_back(sent[pos]);
   }
   else
     loc.push_back(sent[pos]);
}