1
$\begingroup$

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}$.

$\endgroup$
1
  • 1
    $\begingroup$ Which expressions have you tried so far? Even if it is incomplete or wrong, please show us your work and your thought. $\endgroup$
    – John L.
    Nov 6, 2018 at 3:06

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
-2
$\begingroup$

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]);
} 
$\endgroup$
2
  • 1
    $\begingroup$ This is not a programming site. $\endgroup$ Nov 6, 2018 at 6:33
  • 1
    $\begingroup$ This is not a regular expression. $\endgroup$ Nov 6, 2018 at 6:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.