regular expression

simple · **Joined:** Mon, 21 Jun 2004 15:56:08 UTC **Posts:** 69

Let $\Sigma = \left\{ a,b \right\}$ and the set of all string in $\Sigma^\ast$ that start with an even number of a's and no more than two b's.

I only got the first part which is (aa)+(aa)* -> even numbers of a's, however, I don't know how to get the second part for b's.. Can anyone help?

Bilbo · **Posted:** Wed, 1 Feb 2006 19:28:44 UTC

I'm interpreting the description as "starting with an even number of a's followed by no more than two b's." So after the optional b's, the next letter if any must be an a. Also zero is an even number.

The result is: (aa)*b?b?(a[ab]*)?

BTW, in (aa)+(aa)*, the (aa)* is redundant since the + means 1 or more.

Guest · **Posted:** Wed, 1 Feb 2006 22:35:25 UTC

If Bilbos interpretation is correct you could write (haven't tested it)

(aa)*b{,2}

Matt · **Joined:** Wed, 1 Oct 2003 04:45:43 UTC **Posts:** 9631

Bilbo · **Posted:** Thu, 2 Feb 2006 02:15:02 UTC

This is a tricky problem! Here is a regular expression testing program. Using it, I found all of our solutions do not work. But a combination of the three solutions does with the addition of using the start ^ and end $ metacharacters.

Code:

#!/usr/bin/perl
(print "$ARGV[1] matches $ARGV[0]\n"), exit(0) if $ARGV[1] =~ /$ARGV[0]/;
print "$ARGV[1] does not match $ARGV[0]\n";

Here are some results.

~ % re "(aa)*b{0,2}" aaabb
aaabb matches (aa)*b{0,2}

~ % re "(aa)*|(aa)*ba*|(aa)*ba*ba*" aaabb
aaabb matches (aa)*|(aa)*ba*|(aa)*ba*ba*

After trial and error, I found that excluding the odd beginning a and the 3rd b are the tough parts. Here's what I ended up with. It's pretty ugly, so I'd like to see it simplified.

~ % re "^((aa)*|(aa)*b{1,2}(a[ab]*)?)$" aabb
aabb matches ^((aa)*|(aa)*b{1,2}(a[ab]*)?)$

~ % re "^((aa)*|(aa)*b{1,2}(a[ab]*)?)$" aabbb
aabbb does not match ^((aa)*|(aa)*b{1,2}(a[ab]*)?)$

~ % re "^((aa)*|(aa)*b{1,2}(a[ab]*)?)$" aaab
aaab does not match ^((aa)*|(aa)*b{1,2}(a[ab]*)?)$

simple · **Joined:** Mon, 21 Jun 2004 15:56:08 UTC **Posts:** 69

Sorry about the misinterpretation part. It should be start with an even number of a's, and contain no more than 2 b's. So I believe all strings include

aa,aab,aabb
aabaa,aabaab,aaaa
aaaabb,aaaabaaaab, aaaaaa, etc...

Bilbo · **Posted:** Thu, 2 Feb 2006 08:11:01 UTC

That's much better: ^(aa)*(ba*){0,2}$ seems to work.

The strings starting with b and containing at most two b's are included.

simple · **Joined:** Mon, 21 Jun 2004 15:56:08 UTC **Posts:** 69

Hi Bilbo,

The string need to be begin with even number of a's and contains at most 2 b's...

Bilbo · **Posted:** Thu, 2 Feb 2006 09:46:47 UTC

Hi Simple,

As I said before, 0 is an even number, so I think even the empty string fits the description (0 = even # of a's and 0 <= 2 b's). But you can change 1 character to get the result you want. I'll leave that to you.

Thanks for the posting the question. I got something out of it.

Bilbo

S.O.S. Mathematics CyberBoard

regular expression

Who is online