• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 440
  • Last Modified:

regular expression // shortest word


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 !
  • 2
1 Solution
is this a kind of arithmetic phrase?
or a real regexp?

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.
perdoname_Author Commented:
so the second is b and for the third is ab ???
That's what I get.
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

Featured Post

Cloud Class® Course: Microsoft Exchange Server

The MCTS: Microsoft Exchange Server 2010 certification validates your skills in supporting the maintenance and administration of the Exchange servers in an enterprise environment. Learn everything you need to know with this course.

  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now