Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number
 
PerlMonks  

Regex Homework

by chuleto1 (Beadle)
on Feb 24, 2004 at 04:41 UTC ( [id://331306]=perlquestion: print w/replies, xml ) Need Help??

chuleto1 has asked for the wisdom of the Perl Monks concerning the following question:

Wise Monks,
Yes, this is homework. I'm looking for explanation, not just the answer
I would like to enlist your help in coming up with two general regular expressions. Perl code is not necessary only general regular expression notation. Thank you,
1)The set of strings over {a,b,c} with an odd number of occurences of the substring ab

2)The set of strings over {a,b} with an even number of a's or an odd number of b's

Thanks again
OK! people solution for problem 1: (b U a*c)* a+b (b U a*c)* ((b U a*c)* a+b (b U a*c)* a+b (b U a*c)*)*
Comments?

Replies are listed 'Best First'.
Re: Regex Homework
by Corion (Patriarch) on Feb 24, 2004 at 07:15 UTC

    A good approach to abstract problems with regular expessions is to write down some concrete examples and then look at these to see a common pattern emerging. I will not do the complete work for you, because much of the process lies in thinking about what "good" concrete examples are, and in thinking about whether you did find all relevant examples or not.

    For your case a), the following list could be interesting:

    abc abababc ababcab abcabab abcabcab abcabcccccccccccccccab

    Another thing that will be helpfull for you to meditate over is the relation between the terms "odd" and "even". A nonnegative whole number is called "odd", if the number before it is called "even". A number is called "even", if the number before it is called "odd", or if it is zero.

    If you still have problems going forward with this, start with an easier example:

    • c1) Find a regular expression that matches exactly any string consisting of an even number of "d". The empty string is also considered to contain an even number of "d".
    • c2) Modify that regular expression so that it matches exactly any string consisting of an odd number of "d".
Re: Regex Homework
by Zaxo (Archbishop) on Feb 24, 2004 at 07:21 UTC

    The reason this smelled so of homework is that many instructors love these tricky regex puzzles. "Do <whatever> with a single regex" whether or not that is a sane thing to do. Most such problems are better solved with several regexen or other constructs, all pasted together with a bit of logic.

    Your problems each consist of two distinct logical requirements.

    1. An alphabet, and
    2. A condition on the number of certain substrings.
    The first is most easily handled with a negative binding of a negated character class.
    sub is_abc { local $_ = shift || $_; $_ !~ /[^abc]/ } sub is_ab { local $_ = shift || $_; $_ !~ /[^ab]/ }
    Those subs could easily be autoloaded.

    The arithmetic tests differ, and their best implementation may or may not involve a regex match. The odd number of ab pairs is easily implemented with a global one, together with bitwise &,

    sub has_odd_ab { local $_ = shift || $_; my $n = () = /ab/g; # count matches 1 & $n # odd? }
    The condition for the second problem is better done with tr///, because it is quicker for counting individual characters. However it looks, tr/// is not really a regex solution. The logical or appearing in the condition allows a tidy way to package those conditions.
    sub odd_a { local $_ = shift || $_; 1 & tr/a//; } sub odd_b { local $_ = shift || $_; 1 & tr/b//; }
    and the solutions,
    sub prob_one { local $_ = shift || $_; is_abc and has_odd_ab; } sub prob_two { local $_ = shift || $_; is_ab and ! odd_a or odd_b; }
    All that localizing of $_ is to allow $_ to be the default argument without causing any modifications to it.

    After Compline,
    Zaxo

Re: Regex Homework
by graff (Chancellor) on Feb 24, 2004 at 05:06 UTC
    I tend to side with mildside. Show us that you have tried something on your own -- and show us how it failed to do what you really wanted it to do, given a specific input that is relevant to your problem. (Personally, I'm having trouble understanding what you really want, so if you could add some trial, error and further explanation, that would help.)
Re: Regex Homework
by TomDLux (Vicar) on Feb 24, 2004 at 14:45 UTC

    The monks are trying to divine a general solution, but I bet if you had been in class last Wednesday, when this was discussed, you would understand the partticular subset of the problem your instructor had in mind.

    --
    TTTATCGGTCGTTATATAGATGTTTGCA

Re: Regex Homework
by ysth (Canon) on Feb 24, 2004 at 17:33 UTC
    Try thinking it out in english. Classical regular expressions have just a few operations. How do you express the concept of "odd number of x's" using only the following phrases one or more times and parentheses:
    x repeated 0 or more times followed by
Re: Regex Homework
by Boots111 (Hermit) on Feb 24, 2004 at 22:28 UTC
    chyleto1~

    You appear to have a solution to problem (1), although I have not thoroughly checked it myself. For problem 2 I would advise breaking it down into smaller chunks.

    Let us say hypothetically that I had a regular expression R that matched all strings with an even number of as. How would I modify it to match an odd number of as? How would I modify it to match an even number of bs? How would I glue these results together?

    The trick I usualy find most helpful for deriving new regular expressions is to start at the ends (or just the left) and work toward the middle. It is also useful to have a set of stock expression that one knows will match certain things (like even numbers of a particular character). That way I can glue these basic blocks together via alternation (|).

    Hope that helps,
    Boots
    ---
    Computer science is merely the post-Turing decline of formal systems theory.
    --???
Re: Regex
by mildside (Friar) on Feb 24, 2004 at 04:52 UTC
    Call me paranoid, but does this smell like homework to you?

    Update: The title of the node and the text has been changed to indicate that this is indeed homework. Original node title was Regex, and there was absolutley no indication that this was homework. The original poster should have indicated that the node had been updated so that I didn't end up with all these blasted '--'.

      The title says 'regex homework' -- I don't think he was trying to pull a fast one, although we would like to see some effort first.

      --CSUhockey3
        See my update - the original post was edited. Unlucky for me. :(
Re: Regex Homework
by markmoon (Deacon) on Feb 24, 2004 at 14:44 UTC
    Just so people reset their "Homework Detectors™" down to stun, chuleto1 does in fact state:

    "Yes, this is homework."

    in his opening sentence.

    That pesky markmoon guy.
    --
    @a = ("a".."z"," ","-","\n");foreach $b ( 12,0,17,10,24,12,14,14,13,26,8,18,26,0,26, 22,0,13,13,0,27,1,4,26,15,4,17,11,26,7,0, 2,10,4,17) {print $a[$b]};print $a[28];
      Yeah, I noticed that there was a bit of a hubbub going on about this thread later on. I also don't think it's right that a node can be altered without indicating an update.

      Anybody could post a crap reply, wait for merlyn or Abigail or someone on their level to come along later and give the correct answer, copy that to their reply and scoop up XP and glory. Completely, changes the context of your post and mine. It's also too bad you took an XP beating there, for a while. Although I'm not that interested in XP, I do see your point.

      Sorry man! Here... have a beer; )

      markmoon

      --
      @a = ("a".."z"," ","-","\n");foreach $b ( 12,0,17,10,24,12,14,14,13,26,8,18,26,0,26, 22,0,13,13,0,27,1,4,26,15,4,17,11,26,7,0, 2,10,4,17) {print $a[$b]};print $a[28];
      Yes, but only after I prompted them with my post. That opening sentence (and 'Homework' in the title) were added only in response to my post.

      So actually, I think my "Homework Detector™" worked rather well.

      Cheers!

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://331306]
Approved by jweed
Front-paged by broquaint
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2024-03-19 05:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found