I want to devise a regular expression for a language with the following conditions:
- the language is over $\{a, b\}$
- the number of $a$ is equal to the number of $b$
- any prefix of any length in the language has at most one more $a$ than $b$ or $b$ than $a$
For example, $ab$, $abba$, $baba$, $baab$, etc are in the language, but $baaabb$ is not; while it has equal $a$ and $b$, the prefix $baaa$ breaks "Rule #3".
I can surmise the language only contains strings of even parity but how do I create the regular expression?
My best attempt is $(ab)^* (ba)^*$. Any number (including zero) of $ab$ follows all three rules, and any number of $ba$ also follows. Concatenating them also follows, but is it exhaustive?