patternMinor
Regular Expression with at least one a, even number of b
Viewed 0 times
expressionnumberwithregularoneleasteven
Problem
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.
Solution
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^$.
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^$.
Context
StackExchange Computer Science Q#117095, answer score: 3
Revisions (0)
No revisions yet.