Regular expression for strings with even number of a's and odd no of b's

Question

Im having a problem in solving the problem:- Its an assignment, i solved it, but it seems to be too long and vague, Can anyboby help me please......

Regular expression for the strings with even number of a's and odd number of b's where the character set={a,b}.

You should post your solution so that people can suggest specific improvements. — Ian Henry, Sep 13 '10 at 07:52
What is the Regex supposed to achieve? How many sequences of 'a's and 'b's are there? Can you show how you solved it and that may help in determining a regex that could do the same. — Lazarus, Sep 13 '10 at 07:53
You dont want to use RegEx here - the assignment should be solved with a simple "dont!" and a few lines of code. — atamanroman, Sep 13 '10 at 09:27
get an idea from my answer here: [How to write regular expression for a DFA using Arden theorem](http://stackoverflow.com/questions/17420332/need-regular-expression-for-finite-automata/17434694#17434694) — Grijesh Chauhan, Jul 03 '13 at 06:47

paxdiablo · Answer 1 · 2010-09-13T10:33:32.547

One way to do this is to pass it through two regular expressions making sure they both match (assuming you want to use regular expressions at all, see below for an alternative):

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

Anything else (and, in fact, even that) is most likely just an attempt to be clever, one that's generally a massive failure.

The first regular expression ensures there are an even number of a with b anywhere in the mix (before, after and in between).

The second is similar but ensures that there's an odd number of b by virtue of the starting a*ba*.

A far better way to do it is to ignore regular expressions altogether and simply run through the string as follows:

def isValid(s):
    set evenA to true
    set oddB to false
    for c as each character in s:
        if c is 'a':
            set evenA to not evenA
        else if c is 'b':
            set oddB to  not oddB
        else:
            return false
    return evenA and oddB

Though regular expressions are a wonderful tool, they're not suited for everything and they become far less useful as their readability and maintainability degrades.

For what it's worth, a single-regex answer is:

(aa|bb|(ab|ba)(aa|bb)*(ba|ab))*(b|(ab|ba)(bb|aa)*a)

but, if I caught anyone on my team actually using a monstrosity like that, they'd be sent back to do it again.

This comes from a paper by one Greg Bacon. See here for the actual inner workings.

score 7 · Answer 2 · edited Sep 09 '18 at 22:46

7

Even-Even = (aa+bb+(ab+ba)(aa+bb)*(ab+ba))*

(Even-Even has even number of Aas and b's both)

Even a's and odd b's = Even-Even b Even-Even

This hsould work

edited Sep 09 '18 at 22:46

Bhargav Rao

50,140
28
121
140

answered Sep 09 '18 at 17:12

Veenu

71
1
1

score 2 · Answer 3 · edited Oct 10 '17 at 19:44

2

This regular expression takes all strings with even number of a's and even number of b's

r1=((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

Now to get regular expression for even a's and odd b's

r2=(b+a(aa+bb)*(ab+ba))((ab+ba)(aa+bb)*(ab+ba)+(aa+bb))*

edited Oct 10 '17 at 19:44

CDspace

2,639
18
30
36

answered Oct 10 '17 at 13:37

Pooja Consul

21
3

score 1 · Answer 4 · edited Sep 13 '10 at 08:25

1

(bb)*a(aa)*ab(bb)*
ab(bb)* a(aa)*
b(aa)*(bb)* .
.
.
.
.
.

there can be many such regular expressions. Do you have any other condition like "starting with a" or something of the kind (other than odd 'b' and even 'a') ?

edited Sep 13 '10 at 08:25

Sjoerd

74,049
16
131
175

answered Sep 13 '10 at 08:00

vandanak

1,122
3
11
13

i was locking for even number of b's and odd number of a's so i modified you Regex (aa)*b(bb)*ba(aa)* and works for me thankx man – Khurram Ali Apr 28 '15 at 22:43

score 1 · Answer 5 · edited Nov 23 '18 at 12:14

1

For even number of a's and b's , we have regex:

E = { (ab + ba) (aa+bb)* (ab+ba) }*

For even number of a's and odd number of b's , all we need to do is to add an extra b in the above expression E.

The required regex will be:

E = { ((ab + ba) (aa+bb)* (ab+ba))* b ((ab + ba) (aa+bb)* (ab+ba))* }

edited Nov 23 '18 at 12:14

Adrian W

4,563
11
38
52

answered Nov 23 '18 at 09:45

Abhinav Rastogi

11
1

Fabian Pijcke · Answer 6 · 2016-10-21T10:54:26.270

I would do as follows:

regex even matches the symbol a, then a sequence of b's, then the symbol a again, then another sequence of b's, such that there is an even number of b's:

even -> (a (bb)* a (bb)* | a b (bb)* a b (bb)*)

regex odd does the same with an odd total number of b's:

odd -> (a b (bb)* a (bb)* | a (bb)* a b (bb)*)

A string of even number of a's and odd number of b's either:

starts with an odd number of b's, and is followed by an even number of odd patterns amongst even patterns;
or starts with an even number of b's, and is followed by an odd number of odd patterns amongst even patterns.

Note that even has no incidence on the evenness/oddness of the a/b's in the string.

regex -> (

b (bb)* even* (odd even* odd)* even*

|

(bb)* even* odd even* (odd even* odd)* even*

)

Of course one can replace every occurence of even and odd in the final regex to get a single regex.

It is easy to see that a string satisfying this regex will indeed have an even number of a's (as symbol a occurs only in even and odd subregexes, and these each use exactly two a's) and an odd number of b's (first case : 1 b + even number of b's + even number of odd; second case : even number of b's + odd number of odd).

A string with an even number of a's and an odd number of b's will satisfy this regex as it starts with zero or more b's, then is followed by [one a, zero or more b's, one more a and zero or more b's], zero or more times.

score 0 · Answer 7 · answered Dec 13 '16 at 13:39

A high-level advice: construct a deterministic finite automaton for the language---very easy, encode parity of the number of as and bs in the states, with q0 encoding even nr. of as and even nr. of bs, and transition accordingly---, and then convert the DFA into a regular expression (either by using well-known algorithms for this or "from scratch").

The idea here is to exploit the well-understood equivalence between the DFA (an algorithmic description of regular languages) and the regular expressions (an algebraic description of regular languages).

rashedcs · Answer 8 · 2017-12-02T03:18:55.673

0

The regular expression are given below :

    (aa|bb)*((ab|ba)(aa|bb)*(ab|ba)(aa|bb)*b)*

edited Dec 02 '17 at 03:18

answered Dec 01 '17 at 18:05

rashedcs

3,588
2
39
40

score 0 · Answer 9 · answered Feb 02 '19 at 05:25

The structured way to do it is to make one transition diagram and build the regular expression from it. The regex in this case will be

(a((b(aa)*b)*a+b(aa)*ab)+b((a(bb)*a)*b+a(bb)*ba))b(a(bb)*a)*

It looks complicated but it covers all possible cases that may arise.

score -1 · Answer 10 · answered Nov 30 '14 at 12:07

-1

the answer is (aa+ab+ba+bb)* b (aa+ab+ba+bb)*

answered Nov 30 '14 at 12:07

Nishant Chaturvedi

1
1

it can accept baaab that have odd number of a's and even number of b's – Daniel.V Apr 18 '16 at 19:39

score -1 · Answer 11 · answered Feb 25 '16 at 09:41

-1

(bb)* b (aa)* + (aa)* b (bb)*

This is the answer which handles all kind of strings with odd b's and even a's.

answered Feb 25 '16 at 09:41

Balachandhar Nallasivan

1
1

score -2 · Answer 12 · answered Dec 18 '16 at 03:51

-2

If it is even number of a's followed by odd number of b's (aa)*b(bb)* should work

if it is in any order (aa)*b(bb)* + b(bb)(aa) should work

answered Dec 18 '16 at 03:51

SBhattacharya

1

score -2 · Answer 13 · answered Apr 09 '17 at 05:20

-2

All strings that have even no of a's and odd no of b's (((aa+bb) * b(aa+bb) * ) + (A +((a+b)b(a+b)) *)) *

here A is for null string. A can be neglected.

if there is any error plz point it out.

answered Apr 09 '17 at 05:20

Hira

1

This question is pretty old and already have couple of answers. Put your efforts to answer new questions. Also have a look at [How do I write a good answer](http://stackoverflow.com/help/how-to-answer) – Denis Krasakov Apr 09 '17 at 05:49

Regular expression for strings with even number of a's and odd no of b's

13 Answers13

Linked