# Regular expression for language over $\{a, b\}$ with equal number of $a$ and $b$, any prefix has at most one more $a$ than $b$ or $b$ than $a$?

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?

Let $$L$$ be the language in question. The requirement that $$|w|_a=|w|_b$$ for each $$w\in L$$ ensures that every $$w\in L$$ has even length. It’s also clear that every non-empty word in $$L$$ must begin with $$ab$$ or $$ba$$.
Suppose that $$w=xy\in L$$, and $$|x|$$ is even. Then $$|x|_a\equiv|x|_b\pmod 2$$, and $$\big||x|_a-|x|_b\big|\le 1$$, so $$|x|_a=|x|_b$$, and it follows immediately that $$x\in L$$ and hence that $$y\in L$$. In particular, there is an $$x\in L$$ such that $$w=abx$$ or $$w=bax$$. The same argument can then be made for $$x$$, and an easy induction on the length of $$w$$ shows that $$w$$ is a concatenation of $$2$$-character words $$ab$$ and $$ba$$. Clearly any such concatenation is in $$L$$, so $$L$$ is precisely the set of such concatenations: $$L$$ is the language described by the regular expression $$(ab\lor ba)^*$$.