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)^*$.