Can this regular expression be further simplified?

Question

I am working on homework for my compiler class, and I have the following problem:

Write a regular expression for all lines a and b containing an odd number a or an odd number b (or both).

After a lot of work on the board, I came up with the following solution:

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

However, this is the most simplified, can I get it? I thought about building a DFA, trying to minimize the number of states there, to see if this simplifies me, but I decided that I would first ask the regular expression gurus on SO.

Answer 1

Take Greg D's recommendation to get started with (aa) * and go from there. Sepp2k is almost right, but the real consideration is that you do not care about another letter. I mean, when you look at the "odd number" limit, you don't care that you are on your line. So insert b * anywhere :)

Sepp2k's answer is almost right, but this is true:

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

To clarify, this regular expression computes all lines with an odd number (first section) and OR with these lines with any lines containing an odd number b.

Answer 2

This should work:

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

Answer 3

I am afraid that I do not believe that your regular expression is spelled correctly. Consider the line:

 aba 

We have several matches, but the fact that this is an odd length means we have to match a single a on the front panel, so:

 (a)(ba) 

But, unfortunately, it is not possible for your second main grouping to match (ba).

When you come across such a restriction, it was easier for me to start with the main restriction and move from there. In this case, your restriction is “odd,” so start with

 a(aa)* 

to force an odd number a and go from there. :)

Answer 4

I think you need to approach the problem differently.

You are trying to match everything that does not even have numbers like a or b .

It would probably be easier to start with something that matches even numbers a and b . All you need to do at this point is to add something to the end that matches the smallest line that you really want to match.