Solved

# regular expression // shortest word

Posted on 2008-11-13
382 Views
Hello,

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 !
0
Question by:perdoname_

LVL 6

Expert Comment

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

0

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.

perdoname:

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.
0

Author Comment

so the second is b and for the third is ab ???
0

LVL 22

Expert Comment

That's what I get.
0

## Featured Post

### Suggested Solutions

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! https://www.google.com/about/careers/students/guide-to-technical-development.html 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 (https://www.experts-exchange.com/articles/28474/The-Case-of-a-Missing-Mobile-Phone.html)". It will help one to understand clearly the steps to track a lost android phone.

#### Need Help in Real-Time?

Connect with top rated Experts

18 Experts available now in Live!