CODEWITHSUNDEEP
regex
Adam Soffer
Adam Soffer

Reputation: 1664

The set of all strings with even number of ‘aba’ over alphabet { a,b }

This is what I've come up with but it leaves out strings such as "baaabba", "bbbaaabba"...

b*a*((aba)a*b*(aba)a*)*b*

Upvotes: 1

Views: 1866

Answers (2)

Kobi
Kobi

Reputation: 138027

No aba

First, let's see how we would match a string with no abas at all. You'd want something like this:

(b|a+bb)*(a*b*)

At each point, we can match bs, but we need to look out for a - we can match an a (or a block of as) only if it is followed by bb. Lastly, near the end of the string, we are free to match a block of as and a block of bs.

Exactly One aba

Next, let's look at words with one aba. This is very similar to what we had before: 

(b|a+bb)*(a+ba(b|a+bb)*)(a*b*)

We have the same pattern with (a+ba(b|a+bb)*) added in the middle - a+ba is our aba block, and (b|a+bb)* after it is again a block of as and bs which doesn't contain aba.
Note that the inner group (the parentheses around a+ba(b|a+bb)*) isn't needed - it's there for readability.

Exactly Two abas

(b|a+bb)*(a+ba(b|a+bb)*)(a+ba(b|a+bb)*)(a*b*)

Even Number of abas

(b|a+bb)*(a+ba(b|a+bb)*a+ba(b|a+bb)*)*(a*b*)

Similar to the previous one, but with a star around the inner group.

Upvotes: 2

Petar Ivanov
Petar Ivanov

Reputation: 93030

This one ^(((?!aba)[ab])*(aba((?!aba)[ab])*aba)*)*$ will do the work.

I assumed that you want the aba substrings not to overlap. In other words ababa is not a match.

Upvotes: 1

Related Questions