views:

80

answers:

2

I am stumped by this practice problem (not for marks):

{w is an element of {a,b}* : the number of a's is even and the number of b's is even }

I can't seem to figure this one out. In this case 0 is considered even. A few acceptable strings: {}, {aa}, {bb}, {aabb}, {abab}, {bbaa}, {babaabba}, and so on

I've done similar examples where the a's must be a prefix, where the answer would be: (aa)(bb) but in this case they can be in any order.

Kleene stars (*), unions (U), intersects (&), and concatenation may be used.

Edit: Also have trouble with this one

{w is an element of {0,1}* : w = 1^r 0 1^s 0 for some r,s >= 1}

+2  A: 

This is kind of ugly, but it should work:

ε U ( (aa) U (bb) U ((ab) U (ba) (ab) U (ba)) )*

For the second one:

11*011*0

Generally I would use a+ instead of aa* here.

NullUserException
Based on the phrasing/symbols this is probably from a theory book, and many of them don't actually introduce the `+` metacharacter. Strictly speaking, it's not part of RE theory, but the Kleene star is. Anyway, `+` is just syntactic sugar for `aa*`, similar to how `a?` is semantically the same as `a U ε`
eldarerathis
@elderathis Yeah, when I took automata theory I had the `+` :)
NullUserException
@NullUserException This looks correct, thank you. I do understand the how these work, but I was having trouble with them. Is there any process you used to help come up with your answers?
Bobby S
@Bobby eldarerathis Had a good answer on how to do that, but it's been deleted. You would be able to see it if you had more than 10k rep points, but apparently you don't.
NullUserException
@NullUserException I guess, I'll just have to work my way up to 10K
Bobby S
@Null and @Bobby: I'll put my answer back up for the reference. Also, @Null, I got lucky and my professor let me use Perl syntax during theory. He said it was okay after I used `|` all over a quiz because I forgot we were supposed to be using `U` :)
eldarerathis
+1  A: 

Edit: Undeleted re: the comments in NullUserException's answer.

1) I personally think this one is easier to conceptualize if you first construct a DFA that can accept the strings. I haven't written it down, but off the top of my head I think you can do this with 4 states and one accept state. From there you can create an equivalent regex by removing states one at a time using an algorithm such as this one. This is possible because DFAs and regexes are provably equivalent.

2) Consider the fact that the Kleene star only applies to the nearest regular expression. Hence, if you have two individual ungrouped atoms (an atom itself is a regex!), it only applies to the second one (as in, ab* would match a single a and then any number - including 0 - b's). You can use this to your advantage in a case where you want something to exist, but you're not sure of how many there are.

eldarerathis