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

regular expression // shortest word

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

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

perdoname:
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.
0
 
perdoname_Author Commented:
so the second is b and for the third is ab ???
0
 
NovaDenizenCommented:
That's what I get.
0

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