0
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.