Same number of a's and b's but never more than three more of one letter than the other when reading left to right

Question

Could I get a hint on how to construct a regular expression for the alphabet {a, b} which accepts all strings that:

1. Have the same number of a's and b's.
2. Reading the string from left to right, the difference between the number of a's and b's never gets bigger than two.

For example:

• aaa is not a valid (because there are 3 a's more than b's)
• aa is not valid (not same number of a's and b's)
• aababb is valid (same number of a's and b's, and cumulative number of a's or b's is never three more than the other)
• [empty string] is valid
• bbaabbaa is valid

Answer 1

It wouldn't be possible if only the first constraint (have the same number of a's and b's) was there. Because of the second constraint there is a solution to your problem.

It's easier to first think of the finite automaton that does your work (I leave this to you as an exercise) and then transform it to a regular expression.

The transformed regex would be: [ (((a | (aab) (ab)*) b)* (((b | bba) (ba)*) a)* ]* (perhaps it can be simplified, also left for you as an exercise).