• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 414
  • 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.

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

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