3
$\begingroup$

I've been working on some regular expression questions, and came across one that I cannot figure out. Working on the language over $\{a, b\}$, the text asks for a regular expression for the language of all words having at least one a and an even number of b's, using only | and * (maybe $\varepsilon$ too). My idea so far has been something like $(a^*ba^*b)^*a^*a(a^*ba^*b)^*a^*$, but this doesn't match cases like bab, bbbab, or baaab.

$\endgroup$
  • 1
    $\begingroup$ What is "|" in this context? Are you referring to the "OR" operator or to the concatenation operator? $\endgroup$ – Yuval Filmus Nov 14 at 15:16
  • $\begingroup$ The "OR" operator $\endgroup$ – Ari Nov 14 at 15:17
  • $\begingroup$ Are you allowed concatenation (which is what your expression uses)? What are you not allowed to use? Can you come up with a regular expression if we don't care about this restriction? $\endgroup$ – Yuval Filmus Nov 14 at 15:18
  • $\begingroup$ Yes, concatenation is fine. The main thing I've noticed would be useful is the + (One or more) operator, which would help me meet the at least condition, but I'm still not sure I understand how to maintain an even number of b's when they're not placed together. $\endgroup$ – Ari Nov 14 at 15:21
  • $\begingroup$ You can implement $^+$ using $^*$. $\endgroup$ – Yuval Filmus Nov 14 at 15:24
3
$\begingroup$

Another way of seeing this which gives a factorized representation is to try to locate the first $a$. It appears after either an odd or an even number of $b$.

If it appears after an even number of $b$ then you only have to check that what follows also has an even number of $b$ which can be done with Yuval's expression $a^*(ba^*ba^*)^*$.

If the first $a$ comes after an odd number of $b$, then you also have to find another $b$ and then check that the rest contains an even number of $b$.

This could be translated as follows: $(bb)^*(a+ba^+b)a^*(ba^*ba^*)^*$. Again, you can replace $a^+$ by $aa^*$.

$\endgroup$
2
$\begingroup$

Let us start with a regular expression for the language of all words over $\{a,b\}$ containing an even number of $b$s: $$ a^*(ba^*ba^*)^*. $$ If we want to guarantee that there is at least one $a$, which just need one of these $a^*$'s to be $a^+$: $$ a^+(ba^*ba^*)^* + a^*(ba^*ba^*)(ba^+ba^* + ba^*ba^+)(ba^*ba^*). $$ (This can be simplified by replacing some instances of $ba^*ba^*$ by $bb$.)

Finally, you can eliminate $a^+$ by replacing it with $aa^*$.

$\endgroup$
2
$\begingroup$

Take the OR of these three expressions:

$(a^*ba^*b)^* (aa^*ba^*b) (a^*ba^*b)^* a^*$

$(a^*ba^*b)^* (a^*baa^*b) (a^*ba^*b)^* a^*$

$(a^*ba^*b)^* aa^*$

You need any number of groups with two b’s, with any number of a’s in front of each b, followed by any number of a’s. That gives you the even number of b’s, but you need another a. You can add the a in front of a b at an odd position, or in front of a b in an even position, or after all the b’s.

State machine is a lot easier. Four states for odd/even number of b’s, and any a’s or no a, with obvious transitions. Not only is the state machine easier, it’s also much easier to find.

$\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.