Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Given the regular expression (1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 )(1 + $\epsilon$ + 0 ), how many distinct strings would this evaluation produce? How is the word "distinct" interpreted within the regex context? Could you kindly explain?

share|improve this question
add comment

1 Answer 1

up vote 0 down vote accepted

Here are some of the strings it matches (with e for epsilon):

1111
e111
0111
1e11
ee11
0e11
1011
e011
0011
11e1
e1e1
...

removing the epsilon

1111
111
0111
111  !
11
011
1011
011  !
0011
111  !
11   !
...

hi-lighted are the ones that were counted twice.

To count the number of strings it matches without duplicates we can count the number of length 1, length 2, length 3 and length 4 strings it matches (and add them). Each of these are 2^1, 2^2, 2^3, 2^3 so the sum is 2^4-1 = 31.

share|improve this answer
    
Thanks @sperners lemma! –  xupv5 Nov 24 '12 at 8:11
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.