CODEWITHSUNDEEP
regex
DerpDude21
DerpDude21

Reputation: 35

Regex expression for odd # of a's and odd # of b's

I need to create a regex in the language {a,b} that accepts all string with an odd number of a's and an odd number of b's.

Here is my latest and closest try:

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

The grader says that it failed on "", which I assume means it accepts lambda but I do not see how. This does not mean that this is the only thing wrong.

Help please!

Upvotes: 0

Views: 7673

Answers (1)

trincot
trincot

Reputation: 350310

Your attempt has several issues:

  • Indeed "" is matched (and shouldn't): all parts of your regular expression are optional
  • abab, abba, ... etc would be matched as well because ((aa+bb)*(ab+ba))* could be matching an even number of times.
  • The same goes for the second half of the regular expression

Here is one that would do the trick:

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

Here the first (ab+ba) part is not optional, so "" would not match.

There are four states to consider:

  1. even number of a's, even number of b's (initial state)
  2. even number of a's, odd number of b's
  3. odd number of a's, even number of b's
  4. odd number of a's, odd number of b's (target state)

(aa+bb)* is state invariant: the state before the match is the same as the state after the match.

(ab+ba) swaps state 1 with state 4 and vice versa (and state 2 with state 3 and vice versa, but we're not interested in that)

((aa+bb)*(ab+ba)(aa+bb)*(ab+ba))* is state invariant, but it allows the state to go to any other state and come eventually back to the original, ... in all possible ways. When this pattern is executed, the starting state is 4, and so it also exits at that state.

If we take out all the state invariant parts, only (ab+ba) is left over, which transitions the initial state to the target state.

All allowed atomic state changes are covered in this expression.

Upvotes: 3

Related Questions