Regular expression for odd number of a's

Question

I have a problem in solving the following exercise and I'd appreciate any help.

Let Σ = {a,b}. I need to give a regular expression for all strings containing an odd number of a.

Thank you for your time

Answer 1

b*(ab*ab*)*ab*

the main part of it is (ab*ab*)*, which enumerate all possibilities of even number of as. then at last, an extra a has to exist to make it odd.

notice that this regular expression is equivalent to:

b*a(b*ab*a)*b*

these two constructs are in the form defined by pumping lemma:

http://en.wikipedia.org/wiki/Pumping_lemma

---

UPDATE:

@MahanteshMAmbi presented his concern of the regular expression matching the case aaabaaa. In fact, it doesn't. If we run grep, we shall see clearly what is matched.

$ echo aaabaaa | grep -P -o 'b*(ab*ab*)*ab*'
aaabaa
a

-o option of grep will print each matching instance every line. In this case, as we can see, the regular expression is being matched twice. One matches 5 as, one matches 1 a. The seeming error in my comment below is caused by an improper test case, rather than the error in the regular expression.

If we want to make it rigorous to use in real life, it's probably better to use anchors in the expression to force a complete string match:

^b*(ab*ab*)*ab*$

therefore:

$ echo aaabaaa | grep -P -q '^b*(ab*ab*)*ab*$'
$ echo $?
1

Answer 2

^[^a]*a(?=[^a]*(?:a[^a]*a)*[^a]*$).*$

This will find only odd number of a's for any generic string.See demo.

https://regex101.com/r/eS7gD7/22