regular expression // shortest word

Posted on 2008-11-13
Last Modified: 2012-05-05

i've got three regular expressions
 a*(b U abb)b*b
 a*b*b(a U (ab)*)*b*
(a U ab)(a* U ab)*b

and for each to find the shortest word, w µ[belongs]  L(±)

for the first one i thought that the shortest word is bb    and for the 2nd is a* but im not sure for the third one.

any thoughts on this ? or any corrections ?

Thanks in advance for any help !
Question by:perdoname_
    LVL 6

    Expert Comment

    is this a kind of arithmetic phrase?
    or a real regexp?

    LVL 22

    Accepted Solution

    Talmash: grep and perl style regexps have their origin in mathematics, and this is the kind of regular expression the question is about.

    Your answer bb for the first is right.

    There is a simple recursive procedure you can follow to reduce any regular expression to it's minimal string.

    Any literal reduces to itself.

    (x*): this reduces to epsilon (the length-zero string)

    (I'm using + for the union cup symbol since I can't get it to appear correctly).
    x+y:  first reduce x and y to their minimal strings.  Then reduce (x+y) to the shorter of the alternatives.

    xy:  reduce both x and y to their minimal strings, then concatenate those strings.

    Author Comment

    so the second is b and for the third is ab ???
    LVL 22

    Expert Comment

    That's what I get.

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    Introduction On a scale of 1 to 10, how would you rate our Product? Many of us have answered that question time and time again. But only a few of us have had the pleasure of receiving a stack of the filled out surveys and being asked to do somethi…
    Foreword (May 2015) This web page has appeared at Google.  It's definitely worth considering! How to Know You are Making a Difference at EE In August, 2013, one …
    To add imagery to an HTML email signature, you have two options available to you. You can either add a logo/image by embedding it directly into the signature or hosting it externally and linking to it. The vast majority of email clients display l…
    This video is in connection to the article "The case of a missing mobile phone (". It will help one to understand clearly the steps to track a lost android phone.

    730 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    18 Experts available now in Live!

    Get 1:1 Help Now