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

Fifteenth

Sure. For example all strings having abba repeated one or more times is described by the following: Σ*(abba)+Σ* – Fifteenth

Note this should be on the CS Stack Exchange, it's not a programming question. – Cowgirl

My bad - I know better now – Fifteenth

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

Fireguard

@MahanteshMAmbi you missed the stars after bs inside of the parenthesis my friend. – Fireguard

@MahanteshMAmbi $ echo aaabaaa | grep -P 'b*(ab*ab*)*ab*' --> aaabaaa – Fireguard

@MahanteshMAmbi to help you understand further why this is complete as regular expression. in pumping lemma, regular expression is defined to be generated in the form of pr*q, there is only one star of an expression r. therefore I for sure know it covers all the cases. for more details, you can read the pumping lemma page i pasted up there. – Fireguard

@HuStmpHrrr : I think the question is about word having odd numbers of a's. So aaabaaa is not a valid word. Your regular expression must not allow even number of a's. – Tradescantia

@HuStmpHrrr : Thanks for bringing aaabaaa example, the question was asked to give a regular expression which doesn't contain even no of a's. Anyway aaabaa will be accepted by your regular expression but aaabaaa shouldn't be. But it does. So it's wrong is what I am claiming – Tradescantia

@MahanteshMAmbi I updated the answer. that should answer you question. the original answer was correct. – Fireguard

@HuStmpHrrr: Yeah you were right, aaabaaa would not be accepted by your regular expression. – Tradescantia

@JasonHu I guess you have a follow-up question https://mcmap.net/q/1161831/-does-order-not-matter-in-regular-expressions/823738 – Sweatbox

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

Krys

Thank you but the answer I was looking for is exactly like the one HuStmpHrr provided – Fifteenth