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

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

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

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.

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

• This is not a programming site. Nov 6, 2018 at 6:33
• This is not a regular expression. Nov 6, 2018 at 6:33